Very simple#4898

Very simple

1 sekunt

128 megabaýt

Örän ýeňil

Alice and Bob want to secretly transmit messages to each other. For this, they have developed a random number generator (RNG), which is initialized with three integers: $a_{0}$ a_0, $a_{1}$ a_1, and $n$ . The first elements of the RNG are $a_{0}$ a_0 and $a_{1}$ a_1, and the following elements are constructed as follows:

a_{i + 2} = (a_{i + 1}^{2} + a_{i}^{2}) mod n, i = 0, 1, \dots

a_{i+2} = (a_{i+1}^2 + a_i^2) \bmod n, \quad i = 0, 1, \ldots

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

To create the RNG, they want to write a procedure that calculates the value of $a_{k}$ a_k for a given $k$ . Help them!

\InputFileOne line contains four integers $n$ , $a_{0}$ a_0, $a_{1}$ a_1, and $k$ ( $0 \leq a_{0}, a_{1} < n \leq 200$ 0 \leq a_0, a_1 < n \leq 200, $0 \leq k \leq 1 0^{9}$ 0 \leq k \leq 10^9).

\OutputFilePrint the value of $a_{k}$ a_k.

Mysallar

1-nji mysal

Loading

2-nji mysal

Loading

3-nji mysal

Loading

a_{0}

a_{1}

a_{0}

a_{1}

a_{i + 2} = (a_{i + 1}^{2} + a_{i}^{2}) mod n, i = 0, 1, \dots

a_{k}

a_{0}

a_{1}

0 \leq a_{0}, a_{1} < n \leq 200

0 \leq k \leq 1 0^{9}

a_{k}