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!
One line contains four integers n, a[0]
, a[1]
and k, where 0 ≤ a[k]
, a[k]
< n ≤ 200, и 0 ≤ k ≤ 10^9
.
Print one number a[k]
.