Sea $M = 10^{18} + 31$, el cual es un número primo, y $g = 42$, que es una raíz primitiva módulo $M$, lo que significa que $g^1 \pmod M, g^2 \pmod M, \dots, g^{M-1} \pmod M$ son todos enteros distintos en el rango $[1, M)$. Definamos una función $f(x)$ como el entero positivo más pequeño $p$ tal que $g^p \equiv x \pmod M$. Es fácil ver que $f$ es una biyección de $[1, M)$ a $[1, M)$.

Definamos entonces una secuencia de números de la siguiente manera:

• $a_0 = 960\,002\,411\,612\,632\,915$ (puedes copiar este número del ejemplo);
• $a_{i+1} = f(a_i)$.

Dado $n$, encuentra $a_n$.

Entrada

La única línea de entrada contiene un entero $n$ ($0 \le n \le 10^6$).

Salida

Imprime $a_n$.

Ejemplos

Entrada 1

0

Salida 1

960002411612632915

Entrada 2

1

Salida 2

836174947389522544

Entrada 3

300300

Salida 3

263358264583736303

Entrada 4

1000000

Salida 4

300