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 patern 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^{9}+7 (1000000007).
Input
The first line contains 1 ≤ T ≤ 200, the number of testcases.Each testcase contains four numbers N, a, b, X_{1}:
1 ≤ N ≤ 2*10^{7}, the number of tomatoes.
0 ≤ a, b, X_{1} < 10^{9}+7  described above (X_{1} is the size of first tomato).
Sum of N over all testcases will not exceed 5*10^{7}.
Output
For each testcase output the sum of all prices modulo 10^{9}+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
neha1824:
20181111 18:16:16
Quick sort gives TLE.


abhu:
20181107 10:54:47
Radix sort gives TLE. Any modifications required for RADIX? 

ssinghal17:
20181017 17:12:12
can anyone plz halp me in my code. my code is giving TLE after sorting can anyone tell me optimize mathod. 

manya_cod4:
20171217 17:16:27
I used the concept of merging k sorted list, but still its giving me TLE. :( 

tarun2619:
20170708 12:54:13
My submission showed wrong answer on the judge. Can anyone suggest a corner case that may be helpful ?? 

tarun2619:
20170708 12:53:35
Last edit: 20170708 12:55:46 

useandthrowone:
20170328 20:03:10
using n*logn merge sort giving TLE... Can some one suggest other algo/method...


morass:
20170323 17:14:51
@Vipul Srivastava: Thanks  it is nice to hear.


Vipul Srivastava:
20170323 13:14:10
Thanks a lot you really reply fast and help a lot on all the questions you set and it goes without saying your questions are awesome..!! 

morass:
20170323 09:37:17
@Vipul Srivastava: It is required  and can't say: 10 seems pretty much. The problem is designed so that log(N) overhead won't pass (but like this it is very hard to say, what is meant by such constant  if it is meant as executing some linear function which already has some overhead 10 times, or if it really means 10 simple linear cycles {the second version shall pass imho})

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