Soit $M = 10^{18} + 31$, qui est un nombre premier, et $g = 42$, qui est une racine primitive modulo $M$, ce qui signifie que $g^1 \pmod M, g^2 \pmod M, \dots, g^{M-1} \pmod M$ sont tous des entiers distincts dans $[1; M)$. Définissons une fonction $f(x)$ comme le plus petit entier positif $p$ tel que $g^p \equiv x \pmod M$. Il est facile de voir que $f$ est une bijection de $[1; M)$ vers $[1; M)$.

Définissons ensuite une suite de nombres comme suit :

• $a_0 = 960\,002\,411\,612\,632\,915$ (vous pouvez copier ce nombre depuis l'exemple) ;
• $a_{i+1} = f(a_i)$.

Étant donné $n$, trouvez $a_n$.

Entrée

La seule ligne de l'entrée contient un entier $n$ ($0 \le n \le 10^6$).

Sortie

Affichez $a_n$.

Exemples

Entrée 1

0

Sortie 1

960002411612632915

Entrée 2

1

Sortie 2

836174947389522544

Entrée 3

300300

Sortie 3

263358264583736303

Entrée 4

1000000

Sortie 4

300