Niech $M = 10^{18} + 31$, co jest liczbą pierwszą, oraz $g = 42$, co jest pierwiastkiem pierwotnym modulo $M$. Oznacza to, że $g^1 \pmod M, g^2 \pmod M, \dots, g^{M-1} \pmod M$ są wszystkimi różnymi liczbami całkowitymi z przedziału $[1; M)$. Zdefiniujmy funkcję $f(x)$ jako najmniejszą dodatnią liczbę całkowitą $p$ taką, że $g^p \equiv x \pmod M$. Łatwo zauważyć, że $f$ jest bijekcją z $[1; M)$ na $[1; M)$.

Zdefiniujmy ciąg liczb w następujący sposób:

• $a_0 = 960\,002\,411\,612\,632\,915$ (tę liczbę można skopiować z przykładu);
• $a_{i+1} = f(a_i)$.

Dla danego $n$ znajdź $a_n$.

Wejście

Jedyna linia wejścia zawiera jedną liczbę całkowitą $n$ ($0 \le n \le 10^6$).

Wyjście

Wypisz $a_n$.

Przykład

Wejście 1

0

Wyjście 1

960002411612632915

Wejście 2

1

Wyjście 2

836174947389522544

Wejście 3

300300

Wyjście 3

263358264583736303

Wejście 4

1000000

Wyjście 4

300