设 $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