Cho $M = 10^{18} + 31$ là một số nguyên tố, và $g = 42$ là một căn nguyên thủy modulo $M$, nghĩa là $g^1 \pmod M, g^2 \pmod M, \dots, g^{M-1} \pmod M$ là tất cả các số nguyên phân biệt trong đoạn $[1, M)$. Định nghĩa hàm $f(x)$ là số nguyên dương nhỏ nhất $p$ sao cho $g^p \equiv x \pmod M$. Dễ thấy rằng $f$ là một song ánh từ $[1, M)$ đến $[1, M)$.

Sau đó, ta định nghĩa một dãy số như sau:

• $a_0 = 960\,002\,411\,612\,632\,915$ (bạn có thể sao chép số này từ ví dụ);
• $a_{i+1} = f(a_i)$.

Cho $n$, hãy tìm $a_n$.

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa một số nguyên $n$ ($0 \le n \le 10^6$).

Dữ liệu ra

In ra $a_n$.

Ví dụ

Dữ liệu vào 1

0

Dữ liệu ra 1

960002411612632915

Dữ liệu vào 2

1

Dữ liệu ra 2

836174947389522544

Dữ liệu vào 3

300300

Dữ liệu ra 3

263358264583736303

Dữ liệu vào 4

1000000

Dữ liệu ra 4

300