408673: GYM103260 M Discrete Logarithm is a Joke
Memory Limit:0 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
M. Discrete Logarithm is a Joketime limit per test5 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output
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}$$$.
InputThe only line of input contains one integer $$$n$$$ ($$$0 \le n \le 10^{6}$$$).
OutputPrint $$$a_{n}$$$.
ExamplesInput0Output
960002411612632915Input
1Output
836174947389522544Input
300300Output
263358264583736303Input
1000000Output
300