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}$.