Random Number Generation using Linear Congruential Method

Dongdong is fascinated by randomized algorithms, and the generation of random numbers is the foundation of these algorithms. Dongdong intends to use the Linear Congruential Method to generate a sequence of random numbers. This method requires four non‐negative integer parameters \(m, a, c, X_0\) and generates a sequence \(\{X_n\}\) using the recurrence:

\[ X_{n+1} = (aX_n + c) \bmod m \]

where \(\bmod\) denotes the remainder when divided by \(m\). Because each number in the sequence is only dependent on the previous one, the method exhibits typical random behavior and is widely used (for example, many standard random libraries in C++ and Pascal use a version of this method).

However, impatient Dongdong wants to know the value of \(X_n\) quickly. Since he only needs a random number between \(0\) and \(g-1\), he further takes \(X_n \bmod g\). You are required to compute \(X_n \bmod g\) given \(m, a, c, X_0, n, g\), where \(n\) is the number of iterations.

inputFormat

The input consists of six space-separated integers: \(m\), \(a\), \(c\), \(X_0\), \(n\), and \(g\). Here, \(m, a, c, X_0, g\) are non-negative integers with \(m > 0\) (to avoid division by zero) and \(n\) is a non-negative integer representing the number of iterations for the recurrence. The sequence \(\{X_n\}\) is generated by:

\[ X_{n+1} = (aX_n + c) \bmod m \]

You need to output \(X_n \bmod g\).

outputFormat

Output a single integer: \(X_n \bmod g\).

sample

11 8 7 1 5 3

2