WEIRDFN  Weird Function
Let us define:
 F[1] = 1
 F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1
where M[i] is the median of the array {F[1], F[2], ..., F[i1]}.
The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.
Given a, b, c and n, calculate the sum F[1] + F[2] + .. + F[n].
Input
The first line contains T the number of test cases. Each of the next T lines contain 4 integers : a, b, c and n.
Output
Output T lines, one for each test case, containing the required sum.
Constraints
1 <= T <= 100
0 <= a, b, c < 1000000007
1 <= n <= 200000
Example
Sample Input:
2 1 0 0 3 3 1 2 6
Sample Output:
3 103
hide comments
jayss5:
20200618 23:57:05
Ac in one go !!!! 

sarthak_19:
20200603 09:07:16
My 100th on Spoj


hemansh_31:
20200511 20:41:52
quite similar to the running median problem 2 

vidhan_1234:
20200424 11:39:16
TLE in java....


kiran577:
20200423 19:10:52
Any one got AC using JAVA,even after using priority queue's with fast reader and StringBuffer for output i'm still getting TLE. 

shubham_04_04:
20191206 03:17:03
Getting tle even after using two priority queue and fast reading in java 

maneeshkrpatel:
20191123 22:43:43
Very strict time limit..


roopammishra:
20191101 01:59:26
Don't take modulo of F[1]+F[2]+...+F[n]...Got 1 WA :( 

wingman__7:
20191004 10:05:48
maintain two priority queues, and alternate between those two for storing F[i] 

itachi_2016:
20190924 00:14:12
Any corner test cases we need to take care of?

Added by:  Varun Jalan 
Date:  20100125 
Time limit:  1.116s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  own problem used for Codechef Snackdown Onsite 