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

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

hide comments
2019-10-04 10:05:48
maintain two priority queues, and alternate between those two for storing F[i]
2019-09-24 00:14:12
Any corner test cases we need to take care of?
I am sure my approach is correct, I even took care of overflow. Can anyone help me with some corner test cases?
2019-05-29 22:50:26
Be careful, Take mod of terms only, not the mod for the final answer.
2019-04-18 20:54:52 Aditya
The same solution got accepted in c++ but gave tle in Java.

Last edit: 2019-04-18 20:55:16
2019-03-24 20:53:50
@hp1999 bcoz clearing them using priority_queue.clear() takes O(n) time
2019-03-10 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?
2019-01-17 11:38:02
LESSON LEARNED=priority_queue is faster than multiset
got AC by changing multiset impl. to priority_queue one
2019-01-16 18:09:54
Nice problem, can be done using priority_queue. Choose priority_queue over set, if you are using STL.
2018-05-21 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 :( .
2018-02-13 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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.