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