Very simple

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 a[0] and a[1] , the following elements are constructed like this: a[i+2] = (a[i+1] * a[i+1] + a[i] * a[i]) 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 a[k] for a given k. Help them!

Input

One line contains four integers n, a[0], a[1] and k, where 0 ≤ a[k], a[k] < n ≤ 200, и 0 ≤ k ≤ 10^9.

Output

Print one number a[k].

Examples