ADATOMAT - Ada and Tomato

Ada the Ladybug grows tomatoes. She has a very long furrow full of them. At the day of harvest, she picks all tomatoes, sorts them by size, index them (from 1) and sell them for price of "size × index". How much money will she make, if she sells all of them?

As the nature is very beautiful (and Ada is great mathematician), she found the pattern for sizes of tomatoes. The pattern works in (hopefully well known) way: Let us have tomato of size Xi, then Xi+1 will be counted as Xi+1=Xi*a+b mod M. M (modulo) is equal to 109+7 (1000000007).

Input

The first line contains 1 ≤ T ≤ 200, the number of test-cases.

Each test-case contains four numbers N, a, b, X1:

1 ≤ N ≤ 2*107, the number of tomatoes.

0 ≤ a, b, X1 < 109+7 - described above (X1 is the size of first tomato).

Sum of N over all test-cases will not exceed 5*107.

Output

For each test-case output the sum of all prices modulo 109+7.

Example Input

5 
2 2 3 1
3 1 1 1
5 1 2 1
4 1 0 1
20 5 6 7

Example Output

11
14
95
10
150690584

Sizes of tomatoes for each input

1 5
1 2 3
1 3 5 7 9
1 1 1 1
7 41 211 1061 5311 26561 132811 664061 3320311 16601561 75195297 83007811 375976491 399412248 415039061 632654193 879882454 926530843 985306173 997061239

Added by:Morass
Date:2017-03-02
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-03-22 13:36:22
@Vipul Srivastava: Expected complexity is O(N) - and yes, it might matter
2017-03-21 19:21:45 Vipul Srivastava
What is the expected complexity does constant matter with O(n)?
2017-03-03 23:59:55
@Vipul Srivastava: Hello - it shall not be sufficient.

Have Nice Day ^_^
2017-03-03 20:44:31 Vipul Srivastava
Is O(nlogn) not sufficient for this problem?
2017-03-02 16:50:07
@wisfaq: Good day to you. Well - the sequence you described is (exactly) the sizes of tomatoes before harvest. Anyway as you might see (hopefully), she sorts the tomatoes as soon as she harvests them (so it is same sequence you've described BUT sorted (so basically just in another order :) ))

Hope it is more clear (or well, hope it haven't "persisted" this explanation :P )

Good Luck & Have Nice Day
2017-03-02 16:15:04 wisfaq
If I'm not mistaken the output for fifth example is wrong.
The output is 868650009 and the sizes are:
7, 41, 211, 1061, 5311, 26561, 132811, 664061, 3320311, 16601561, 83007811, 415039061, 75195297, 375976491, 879882454, 399412248, 997061239, 985306173, 926530843, 632654193 as far as I can see.


Last edit: 2017-03-02 16:16:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.