Sphere Online Judge

SPOJ Problem Set (classical)

5977. Weird Function

Problem code: WEIRDFN


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.

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:2010-01-25
Time limit:6s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource:own problem used for Codechef Snackdown Onsite

hide comments
2014-02-02 23:17:12 (Tjandra Satria Gunawan)(曾毅昆)
Time limit is too strict!
2013-05-17 12:42:45 ryuz@Ki
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 ??


Last edit: 2013-05-17 12:56:55
2013-02-03 13:36:52 J.A.R.V.I.S.
Nice one :) solvable with STLs.. Watch out for overflows...
2013-01-27 12:20:48 conioh
nice question...
2012-12-09 20:07:18 Nilendu Das
Good question.. You can take help from RRATING problem from codechef..Jst the partition is diff..
2012-11-19 06:26:53 Paul Draper
This problems "allows" for languages other than C/C++, but the time limit does not.
2012-08-15 03:19:05 Anand
Very nice problem I am getting TLE
2012-08-13 06:18:37 BOND
My inference after several TLE's - sets are slower than queues...
2012-07-12 14:58:56 Nishchay Kala
There is no JAVA submission for this problem, I am trying in JAVA getting TLE, Used inbuilt min/max priority queue.
Any help ?
2012-05-06 21:13:55 Michael T
unsigned long long works just fine
and despite what some people write on the forum stl's priority queue works great as well.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.