FrozenStandings | Topcoder Archive

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 &lt; 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.

Definition

Class:: FrozenStandings
Method:: countStandings
Parameters:: int, int, int
Returns:: int
Method signature:: int countStandings(int N, int A, int seed)
(be sure your method is public)

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

```
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
```
```
565225711
```
```
Returns: 1
```
The array X will be {0}.
```
5
```
```
1
```
```
765276374
```
```
Returns: 27
```
The array X will be {0, 0, 0, 0, 0}.
```
8
```
```
2
```
```
667363653
```
```
Returns: 226
```
The array X will be {1, 0, 1, 1, 1, 0, 1, 1}.
```
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}.
```
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)2024, Topcoder, Inc. All rights reserved.