21094번 - Discrete Logarithm is a Joke 다국어

문제

$M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M,ドル which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer $p$ such that $g^{p} = x \bmod M$. $f$ is a bijection from $[1; M)$ to $[1; M)$.

Let's then define a sequence of numbers as follows:

• $a_{0} = 960,002円,411円,612円,632円,915円$ (you can copy this number from the sample);
• $a_{i + 1} = f(a_{i})$.

Given $n,ドル find $a_{n}$.

입력

The only line of input contains one integer $n$ (0ドル \le n \le 10^{6}$).

출력

Print $a_{n}$.

제한

힌트