시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 5 5 4 100.000%

문제

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

예제 입력 1

0

예제 출력 1

960002411612632915

예제 입력 2

1

예제 출력 2

836174947389522544

예제 입력 3

300300

예제 출력 3

263358264583736303

예제 입력 4

1000000

예제 출력 4

300