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


baddu609:
20190529 22:50:26
Be careful, Take mod of terms only, not the mod for the final answer. 

Aditya:
20190418 20:54:52
The same solution got accepted in c++ but gave tle in Java. Last edit: 20190418 20:55:16 

tanmay2904:
20190324 20:53:50
@hp1999 bcoz clearing them using priority_queue.clear() takes O(n) time


hp1999:
20190310 13:09:31
I can't get it. I got TLE when I declared the priority queues outside the 't' while loop (the one I used for test cases) and was emptying them after each iteration. But when I declared them inside it, I got AC. What could be the reason? 

masterchef2209:
20190117 11:38:02
LESSON LEARNED=priority_queue is faster than multiset


tan_sourabh:
20190116 18:09:54
Nice problem, can be done using priority_queue. Choose priority_queue over set, if you are using STL. 

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