## Day 1, Problem 1 - Random Number Generator

DongDong recently became obsessed with randomization, and random number generators is the foundation of randomization. DongDong plans to use the linear congruential method to generate a number sequence. This method requires for nonnegative integer parameters m, a, c, X0. Then, a random sequence <Xn> can be generated using the following formula:

Xn + 1 = (aXn + c) mod m

where "mod m" means to take the remainder after the left hand expression has divided m. It can be observed from this equation that the next number in a sequence will always be based off of the current number.

Sequences generated this way are very random in nature, which is why this method has been used extensively. Even randomization functions in the widely used standard libraries of C++ and Pascal employ this method.

DongDong knows that sequences produced this way are very random, but he is also impatient about wanting to know the value Xn as soon as possible. Since DongDong needs a random number that's one of 0, 1, …, g − 1, he will have to modulo the number Xn by g to get the final result. All you have to do is determine the value of Xn mod g for DongDong.

### Input Format

The input consists of 6 space-separated integers m, a, c, X0, n, and g. Here, a, c, and X0 are nonnegative while m, n, g are positive.

### Output Format

Output a single integer, the value of Xn mod g.

### Sample Input

`11 8 7 1 5 3`

`2`

### Explanation

The first few terms of <Xn> are:

 k Xk 0 1 2 3 4 5 1 4 6 0 7 8

Thus the answer is X5 mod g = 8 mod 3 = 2.

### Constraints

Test Casenm, a, c, X0m, ag
1n ≤ 100m, a, c, X0 ≤ 100m is primeg ≤ 108
2n ≤ 1000m, a, c, X0 ≤ 1000m is prime
3n ≤ 104m, a, c, X0 ≤ 104m is prime
4n ≤ 104m, a, c, X0 ≤ 104m is prime
5n ≤ 105m, a, c, X0 ≤ 104m and a − 1 are prime
6n ≤ 105m, a, c, X0 ≤ 104m and a − 1 are prime
7n ≤ 105m, a, c, X0 ≤ 104m and a − 1 are prime
8n ≤ 106m, a, c, X0 ≤ 104/
9n ≤ 106m, a, c, X0 ≤ 109m is prime
10n ≤ 106m, a, c, X0 ≤ 109/
11n ≤ 1012m, a, c, X0 ≤ 109m is prime
12n ≤ 1012m, a, c, X0 ≤ 109m is prime
13n ≤ 1016m, a, c, X0 ≤ 109m and a − 1 are prime
14n ≤ 1016m, a, c, X0 ≤ 109m and a − 1 are prime
15n ≤ 1016m, a, c, X0 ≤ 109/
16n ≤ 1018m, a, c, X0 ≤ 109/
17n ≤ 1018m, a, c, X0 ≤ 109/
18n ≤ 1018m, a, c, X0 ≤ 1018m is prime
19n ≤ 1018m, a, c, X0 ≤ 1018m is prime
20n ≤ 1018m, a, c, X0 ≤ 1018/

For all of the test cases: n, m, g ≥ 1, and a, c, X0 ≥ 0.

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 512M