Random Number Generator

Hongjun became interested in random sampling while studying statistics. He wants to generate random numbers from a sequence defined by a linear recurrence.

The sequence is determined by nonnegative integers m, a, c, and X0. The sequence X_n is defined as follows.

X_{n+1} = (aX_n + c) mod m

Here, A mod m means the remainder when A is divided by m.

The final random number is the remainder when X_n is divided by a positive integer g. Therefore, the generated random number is an integer from 0 to g-1, inclusive.

Given the values, write a program that computes X_n mod g.

The first line contains six integers m, a, c, X0, n, and g in that order.

m, a, c, X0, and n are at most 10^18, and g is at most 10^8. The values a, c, and X0 are nonnegative integers, while m, n, and g are positive integers.

Print the value of X_n mod g on the first line.

For the first public test case, the generated sequence X_n is as follows.

Thus, X_5 mod g = 8 mod 3 = 2.