Alice and Bob want to secretly transmit messages to each other, and for this they have developed a random number generator (RNG), which is initialized with three integers: a [0], a [1] and n. The first elements of the RNG are a0 and a1, the following elements are constructed like this: ai+2 = (ai+1 * ai+1 + ai * ai) mod n, i = 0, 1, ...

Alice and Bob will use the RNG in the data transfer scheme, as shown in the figure.

To create a RNG, they want to write a procedure that calculates the value of ak for a given k. Help them!

Input

One line contains four integers n, a0, a1 and k, where 0 ≤ ak, ak < n ≤ 200, и 0 ≤ k ≤ 109.

Output

Print one number ak.