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
Harpreet Singh:
20141204 18:26:36
strict^strict timelimit 

Kunal Behl:
20140913 15:53:45
y time limit exceed everytime?? can anybody help please..


Matija Martiniæ:
20140604 21:24:16
TLE even after using stl heap c++... :(


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140202 23:17:12
Time limit is too strict! 

SaSukE:
20130517 12:42:45
why implementation using red black tree is giving TLE ?? :/....Insertion and every query takes O(logn) still getting TLE ?? What should be the complexity of the solutn ??


J.A.R.V.I.S.:
20130203 13:36:52
Nice one :) solvable with STLs.. Watch out for overflows... 

conioh:
20130127 12:20:48
nice question... 

Nilendu Das:
20121209 20:07:18
Good question.. You can take help from RRATING problem from codechef..Jst the partition is diff.. 

Paul Draper:
20121119 06:26:53
This problems "allows" for languages other than C/C++, but the time limit does not. 

Anand:
20120815 03:19:05
Very nice problem I am getting TLE 
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 