Problem Statement

The final round of Top Cat Open 2014 is over! However, we do not know the final
standings yet because the scoreboard has been frozen for the last hour.  

There are N contestants in the final round. They are numbered 0 through N-1
according to the results of the previous round. According to the frozen
standings, contestant i has already solved X[i] problems. After the standings
have been frozen, each contestant was only allowed to solve one additional
problem. Thus, for each i the actual number of problems solved by contestant i
is either X[i] or X[i] + 1.  

In the final standings the contestants will be ordered by the number of
problems solved (more is better). In case of a tie the contestant with a
smaller number will have the better place.  

The array X is generated from given ints A and seed. Use the following
pseudocode to generate X:

64bit_integer x = seed;
for (i = 0; i < N; i++) {
    x = x * 20142014 % 1000000007;
    X[i] = x % A;
}

How many different rankings are possible at the end of the contest? Return this
value modulo 1,000,000,007.



Method signature: int countStandings(int N, int A, int seed)
Time limit (s): 2.000
Memory limit (MB): 256


Constraints

- N will be between 1 and 500,000, inclusive.
- A will be between 1 and 500,000, inclusive.
- seed will be between 1 and 1,000,000,006, inclusive.


Examples

0)

3
3
2137378
Returns: 2

The array X will be {0, 2, 2}. If contestant 2 solved one more problem during
the last hour but contestant 1 did not, the final ranking will be (2,1,0).
Otherwise the final ranking will be (1,2,0).


1)

1
1
565225711
Returns: 1

The array X will be {0}.


2)

5
1
765276374
Returns: 27

The array X will be {0, 0, 0, 0, 0}.


3)

8
2
667363653
Returns: 226

The array X will be {1, 0, 1, 1, 1, 0, 1, 1}.


4)

20
4
765276374
Returns: 933806

The array X will be {3, 3, 2, 3, 1, 0, 3, 1, 3, 0, 1, 3, 2, 1, 0, 1, 0, 3, 2, 1}.


5)

500000
100
123456789
Returns: 482934470


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.