408673: GYM103260 M Discrete Logarithm is a Joke

Let's take $$$M = 10^{18} + 31$$$ which is a prime number, and $$$g = 42$$$ which is a primitive root modulo $$$M$$$, which means that $$$g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$$$ are all distinct integers from $$$[1; M)$$$. Let's define a function $$$f(x)$$$ as the smallest positive integer $$$p$$$ such that $$$g^{p} \equiv x \pmod M$$$. It is easy to see that $$$f$$$ is a bijection from $$$[1; M)$$$ to $$$[1; M)$$$.

Let's then define a sequence of numbers as follows:

• $$$a_{0} = 960\,002\,411\,612\,632\,915$$$ (you can copy this number from the sample);
• $$$a_{i + 1} = f(a_{i})$$$.

Given $$$n$$$, find $$$a_{n}$$$.

The only line of input contains one integer $$$n$$$ ($$$0 \le n \le 10^{6}$$$).

Print $$$a_{n}$$$.

0

960002411612632915

1

836174947389522544

300300

263358264583736303

1000000

300