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 X_i, then X_i+1 will be counted as X_i+1=X_i*a+b mod M. M (modulo) is equal to 10⁹+7 (1000000007).

Input

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

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

1 ≤ N ≤ 2*10⁷, the number of tomatoes.

0 ≤ a, b, X₁ < 10⁹+7 - described above (X₁ is the size of first tomato).

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

Output

For each test-case output the sum of all prices modulo 10⁹+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

---

hide comments

< Previous 1 2 Next >
	morass: 2017-03-22 13:36:22 @Vipul Srivastava: Expected complexity is O(N) - and yes, it might matter
	Vipul Srivastava: 2017-03-21 19:21:45 What is the expected complexity does constant matter with O(n)?
	morass: 2017-03-03 23:59:55 @Vipul Srivastava: Hello - it shall not be sufficient. Have Nice Day ^_^
	Vipul Srivastava: 2017-03-03 20:44:31 Is O(nlogn) not sufficient for this problem?
	morass: 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
	wisfaq: 2017-03-02 16:15:04 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