Problem E
Disastrous Downfall
There is a heavy rainfall over the Antique Cultural Museum, and the roof has sprung a leak! All the beautiful paintings risk destruction, if it weren’t for one brave night watchman standing in the water’s way – Klunkas Plaskocek.
To protect all of the paintings, Klunkas has brought $N$ buckets and placed them in a long row to catch the water falling from the ceiling. Each bucket can hold exactly $K$ drops of water. If a drop falls into a bucket which is full, the water drop will overflow to the bucket standing to the left. If that bucket is full as well, the drop will keep flowing left until there is a non-full bucket.
Klunkas needs your help to prevent the leftmost bucket overflowing. After every drop of water falls, Klunkas wants to know which bucket it ended up in, so that he can keep track of the water levels of the buckets.
Due to the very regular nature of rain, Klunkas figured that the $R$ rain drops fall in a very nice pattern. Given constants $X_0, A, B$, we define the sequence $X_ i$ as
\[ X_ i = (A \cdot X_{i-1} + B) \mod N \]The bucket which the $i$-th rain drop falls into, is then $X_ i$ for $i = 1, \dots , R$. The leftmost bucket has the number $0$, and the rightmost bucket has the number $N-1$.
Input
Input consists of the space-separated integers $1 \le N \le 10^6$, $1 \le R \le 10^7$, $1 \le K \le 10$, $0 \le X_0, A, B \le 2^{31} - 1$.
Output
If the leftmost bucket overflows, output “OVERFLOW”.
Otherwise, the output should be calculated as follows:
Let $O_ i$ be the bucket which the $i$:th rain drop ended up in, and let $a = 0$.
Then, for every $i$ from $1$ to $R$, set $a := (53 \cdot a + O_ i) \mod 199933$.
The output should then be a line with the integer $a$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 6 1 2 1 8 |
OVERFLOW |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 6 1 4 1 8 |
79732 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 20 2 8 7 3 |
31786 |
