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
taponidhi:
20180521 12:57:32
It's a really gud question with nice STL implementation.Just remember to not take modulus of ∑F(i).If you take modulus,it will give wrong answer.I was kinda stuck there :( . 

shahianshu:
20180213 12:22:38
question can be solved in c++ by using priority queue stl by making two priority queue left and right and taking the middle as integer and forming logic based on the question. 

n_k_rathi:
20160621 07:27:00
Hi,


5e9f0u1t:
20151214 21:02:05
bad question..try optimising number of modulo operations


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