给定 \(M = 10^{18} + 31, g = 42\)，\(g\) 是模 \(M\) 意义下的原根。设 \(f(x)\) 表示满足 \(g^y \equiv x \pmod M\) 的最小正整数 \(y\)（即 \(x\) 的离散对数）。我们有 \(a_0 = 960002411612632915, a_n = f(a_{n - 1})\)，求 \(a_n\)（\(0 \le n \le 10^6\)）。
样例输入 1
0样例输出 1
960002411612632915样例输入 2
1样例输出 2
836174947389522544样例输入 3
300300样例输出 3
263358264583736303样例输入 4
1000000样例输出 4
300
离散对数你不会求，离散指数你还不会求吗？
发现样例已经告诉你 \(a_{10^6}\) 了，反过来求 \(a_n\) 就完了。