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.
Example
Sample Input :
2
1 0 0 3
3 1 2 6
Sample Output :
3
103
Constraints
1 <= T <= 100
0 <= a,b,c < 1000000007
1 <= n <= 200000
Added by:  Varun Jalan 
Date:  20100125 
Time limit:  1.116s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: NODEJS PERL 6 SCM chicken VB.net 
Resource:  own problem used for Codechef Snackdown Onsite 
hide comments
Harpreet Singh:
20141204 18:26:36
strict^strict timelimit 

SANDIPAN MANDAL:
20141003 20:03:03
Getting WA. Plz provide some corner test cases 

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++... :(


sam17121991:
20140423 19:14:51
oh my gosh! 

(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.. 