SPOJ.com - Problem ADATOMAT

ADATOMAT - Ada and Tomato

#sorting

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

Example Output

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

Submit solution!

hide comments

< Previous 1 2 Next >

	neha1824: 2018-11-11 18:16:16 Quick sort gives TLE. Counting sort gives TLE. Merging k-sorted lists gives TLE Last edit: 2019-09-23 22:14:27
	abhu: 2018-11-07 10:54:47 Radix sort gives TLE. Any modifications required for RADIX?
	ssinghal17: 2018-10-17 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: 2017-12-17 17:16:27 I used the concept of merging k- sorted list, but still its giving me TLE. :(
	tarun2619: 2017-07-08 12:54:13 My submission showed wrong answer on the judge. Can anyone suggest a corner case that may be helpful ??
	useandthrowone: 2017-03-28 20:03:10 using nlogn merge sort giving TLE... Can some one suggest other algo/method... Also using inserting into a sorted array procedure also giving TLE.. Last edit: 2017-03-28 20:03:57*
	morass: 2017-03-23 17:14:51 @Vipul Srivastava: Thanks - it is nice to hear. Well - a few points to your solution: A) 10 is nice because it is easy to think about it - anyway if we "throw off" this fact, there are better decompositions [you can think about how will the "10" show-off in the complexity] B) Currently it is no problem - and perhaps it might not be problem at all, anyway I could also point out, that stl have some "overhead" {hopefully it won't matter, but I can't guarantee it}. So now it won't influence it - but it can be done without it [so just leaving it here - but focus on "A" :) ] Good Luck & Have Nice Day!
	Vipul Srivastava: 2017-03-23 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: 2017-03-23 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}) So sorry for "confusing" answer, yet the "constant" migh/might not pass depending on its meaning and use in practice :/ ~/Morass
	Vipul Srivastava: 2017-03-23 09:06:24 Sorry for repeated comments but I am not able to figure this out. If i sort in O(10*n) using appropriate algo will it pass? Or sorting is not at all required here?

Submit solution!

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