Пусть $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)$ как наименьшее положительное целое число $p$, такое что $g^p \equiv x \pmod M$. Легко видеть, что $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