$M = 10^{18} + 31$ を素数とし、$g = 42$ を $M$ を法とする原始根とします。これは、$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)$ への全単射であることが容易にわかります。

次に、数列を以下のように定義します。

• $a_0 = 960\,002\,411\,612\,632\,915$ （この数値はサンプルからコピーできます）
• $a_{i+1} = f(a_i)$

$n$ が与えられたとき、$a_n$ を求めてください。

入力

入力は1行のみで、整数 $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