$M = 10^{18} + 31$을 소수라 하고, $g = 42$를 $M$에 대한 원시근(primitive root)이라고 합시다. 이는 $g^1 \pmod M, g^2 \pmod M, \dots, g^{M-1} \pmod M$이 $[1, M)$ 범위의 모든 서로 다른 정수임을 의미합니다. 함수 $f(x)$를 $g^p \equiv x \pmod M$을 만족하는 가장 작은 양의 정수 $p$라고 정의합시다. $f$는 $[1, M)$에서 $[1, M)$로 가는 전단사 함수(bijection)임이 쉽게 확인됩니다.

이제 다음과 같이 수열을 정의합니다.

• $a_0 = 960\,002\,411\,612\,632\,915$ (이 숫자는 예제에서 복사할 수 있습니다);
• $a_{i+1} = f(a_i)$.

$n$이 주어질 때, $a_n$을 구하세요.

입력

입력의 첫 번째 줄에는 정수 $n$ ($0 \le n \le 10^6$) 하나가 주어집니다.

출력

$a_n$을 출력하세요.

예제

입력 1

0

출력 1

960002411612632915

입력 2

1

출력 2

836174947389522544

입력 3

300300

출력 3

263358264583736303

입력 4

1000000

출력 4

300