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
jayss5: 2020-06-18 23:57:05

Ac in one go !!!!

sarthak_19: 2020-06-03 09:07:16

My 100th on Spoj

hemansh_31: 2020-05-11 20:41:52

quite similar to the running median problem 2

vidhan_1234: 2020-04-24 11:39:16

TLE in java....

kiran577: 2020-04-23 19:10:52

Any one got AC using JAVA,even after using priority queue's with fast reader and StringBuffer for output i'm still getting TLE.

shubham_04_04: 2019-12-06 03:17:03

Getting tle even after using two priority queue and fast reading in java

maneeshkrpatel: 2019-11-23 22:43:43

Very strict time limit..
got 2 tle due to only taking mod inside the formula also.

Last edit: 2019-11-23 22:47:29
roopammishra: 2019-11-01 01:59:26

Don't take modulo of F[1]+F[2]+...+F[n]...Got 1 WA :(

wingman__7: 2019-10-04 10:05:48

maintain two priority queues, and alternate between those two for storing F[i]

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


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