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}$$$.