WEIRDFN - Weird Function

no tags 

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[i-1]}.

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: 2012-08-13 06:18:37

My inference after several TLE's - sets are slower than queues...

nishchay: 2012-07-12 14:58:56

There is no JAVA submission for this problem, I am trying in JAVA getting TLE, Used inbuilt min/max priority queue.
Any help ?

Michael T: 2012-05-06 21:13:55

unsigned long long works just fine
and despite what some people write on the forum stl's priority queue works great as well.

Yashodhan S. Katte: 2012-03-28 17:53:03

TLE TLE TLE any hint?

Gurpreet Singh: 2011-10-31 21:10:43

Please help.
In which case my code fails?
id=5941347

.::Manish Kumar::.: 2011-03-03 17:28:27

Finally Got AC.
Why did unsigned long long not work while long long did ... ?


Added by:Varun Jalan
Date:2010-01-25
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