令 $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$。

輸入格式

輸入僅包含一行，包含一個整數 $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