Dongdong has recently become fascinated by randomized algorithms, and random number generation is the foundation of such algorithms. Dongdong 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 generating a series of random numbers $\langle X_n \rangle$ according to the following formula:
$$X_{n+1} = (aX_n + c) \pmod m$$
where $X_n \pmod m$ represents the remainder of the previous number divided by $m$. As can be seen from this formula, the next number in the sequence is always generated from the previous one.
Sequences generated using this method possess the properties of random sequences, and thus this method is widely used, including in the random number library functions commonly used in C++ and Pascal.
Dongdong knows that the sequence generated in this way has good randomness, but being impatient, he still wants to know the value of $X_n$ as quickly as possible. Since the random numbers Dongdong needs are between $0, 1, \dots, g-1$, he needs to take the remainder of $X_n$ divided by $g$ to get the number he wants, i.e., $X_n \pmod g$. You only need to tell Dongdong what the number $X_n \pmod g$ he wants is.
Input
The input contains 6 space-separated integers $m, a, c, X_0, n,$ and $g$, where $m, a, c, X_0$ are non-negative integers, and $n, m, g$ are positive integers.
Output
Output a single number, which is $X_n \pmod g$.
Examples
Input 1
11 8 7 1 5 3
Output 1
2
Note
The first few terms of $\langle X_n \rangle$ are:
| $k$ | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| $X_k$ | 1 | 4 | 6 | 0 | 7 | 8 |
Therefore, the answer is $X_5 \pmod 3 = 8 \pmod 3 = 2$.
Constraints
| Test Case ID | $n$ | $m, a, c, X_0$ | $m, a$ Property | $g$ |
|---|---|---|---|---|
| 1 | $n \le 100$ | $m, a, c, X_0 \le 100$ | $m$ is prime | $g \le 10^8$ |
| 2 | $n \le 1000$ | $m, a, c, X_0 \le 1000$ | $m$ is prime | |
| 3 | $n \le 10^4$ | $m, a, c, X_0 \le 10^4$ | $m$ is prime | |
| 4 | $n \le 10^4$ | $m, a, c, X_0 \le 10^4$ | $m$ is prime | |
| 5 | $n \le 10^5$ | $m, a, c, X_0 \le 10^4$ | $m$ and $a-1$ are coprime | |
| 6 | $n \le 10^5$ | $m, a, c, X_0 \le 10^4$ | $m$ and $a-1$ are coprime | |
| 7 | $n \le 10^5$ | $m, a, c, X_0 \le 10^4$ | $m$ and $a-1$ are coprime | |
| 8 | $n \le 10^6$ | $m, a, c, X_0 \le 10^4$ | / | |
| 9 | $n \le 10^6$ | $m, a, c, X_0 \le 10^9$ | $m$ is prime | |
| 10 | $n \le 10^6$ | $m, a, c, X_0 \le 10^9$ | / | |
| 11 | $n \le 10^{12}$ | $m, a, c, X_0 \le 10^9$ | $m$ is prime | |
| 12 | $n \le 10^{12}$ | $m, a, c, X_0 \le 10^9$ | $m$ is prime | |
| 13 | $n \le 10^{16}$ | $m, a, c, X_0 \le 10^9$ | $m$ and $a-1$ are coprime | |
| 14 | $n \le 10^{16}$ | $m, a, c, X_0 \le 10^9$ | $m$ and $a-1$ are coprime | |
| 15 | $n \le 10^{16}$ | $m, a, c, X_0 \le 10^9$ | / | |
| 16 | $n \le 10^{18}$ | $m, a, c, X_0 \le 10^9$ | / | |
| 17 | $n \le 10^{18}$ | $m, a, c, X_0 \le 10^9$ | / | |
| 18 | $n \le 10^{18}$ | $m, a, c, X_0 \le 10^{18}$ | $m$ is prime | |
| 19 | $n \le 10^{18}$ | $m, a, c, X_0 \le 10^{18}$ | $m$ and $a-1$ are coprime | |
| 20 | $n \le 10^{18}$ | $m, a, c, X_0 \le 10^{18}$ | / |
For all data, $n \ge 1, m \ge 1, a \ge 0, c \ge 0, X_0 \ge 0, g \ge 1$.