Description

Dongdong has recently become fascinated with randomized algorithms, and random numbers are the foundation for generating them. He plans to use the Linear Congruential Method to generate a sequence of random numbers. This method requires setting four non-negative integer parameters $m, a, c, X_0$, and generates a sequence $\{X_n\}$ according to the formula:

Here, $\bmod m$ denotes the remainder when the preceding number is divided by $m$. From this equation, we can see that the next number in the sequence is always determined by the previous one.

Sequences generated by this method have properties of random sequences, so it is widely used. The standard library functions for generating random numbers in C++ and Pascal also use this method.

Dongdong knows that the sequence produced this way has good randomness, but he is impatient and wants to know $X_n$ as soon as possible. Since the random numbers he needs are between $0, 1, \dots, g - 1$, he will take $X_n$ modulo $g$ to get the number he wants, i.e., $X_n \bmod g$. You only need to tell Dongdong the value of $X_n \bmod g$.

Input Format

One line contains 6 space-separated integers $m, a, c, X_0, n$ and $g$, where $a, c, X_0$ are non-negative integers, and $m, n, g$ are positive integers.

Output Format

Output a single number, which is $X_n \bmod g$.

11 8 7 1 5 3

2

Hint

We compute $X_n = X_5 = 8$, thus $(X_n \bmod g) = (8 \bmod 3) = 2$.

Constraints: For $100\%$ of the testdata, $n, m, a, c, X_0 \leq 10^{18}$, $1 \leq g \leq 10^8$, $n, m \geq 1$, $a, c, X_0 \geq 0$.

Translated by ChatGPT 5