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
BOND:
20120813 06:18:37
My inference after several TLE's  sets are slower than queues... 

nishchay:
20120712 14:58:56
There is no JAVA submission for this problem, I am trying in JAVA getting TLE, Used inbuilt min/max priority queue.


Michael T:
20120506 21:13:55
unsigned long long works just fine


Yashodhan S. Katte:
20120328 17:53:03
TLE TLE TLE any hint? 

Gurpreet Singh:
20111031 21:10:43
Please help.


.::Manish Kumar::.:
20110303 17:28:27
Finally Got AC.

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 