Discrete Logarithm is a Joke

시간 제한10초메모리 제한256 MB

요약

소수 M과 원시근 g, 이산 로그 함수 f가 주어질 때 고정된 a0에서 시작해 f를 n번 적용한 값을 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

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

예제4

예제 1
입력
```
0
```
예상 출력
```
960002411612632915
```
예제 2
입력
```
1
```
예상 출력
```
836174947389522544
```
예제 3
입력
```
300300
```
예상 출력
```
263358264583736303
```
예제 4
입력
```
1000000
```
예상 출력
```
300
```