Fibonacci-th Fibonacci

解説

mod $M$ のフィボナッチ数列の周期を$f(M)$とします。$M=998244353$から始めて$M$を$f(M)$で置き換える操作を繰り返すと

$$\begin{aligned} 998244353 \to 1996488708\to 27710040 \\ \to2341560\to32760\to1680 \to240\to120 \end{aligned}$$

と変化し、$120$以降は$120$がループすることが分かります。$g(N,K,M)$をこの問題の答えを$M$で割った余りとすると、

$$g(N,K,M)= \begin{cases} F_{g(N,K-1,f(M))}\quad mod\, M & \text{if K>0}\\ N \quad mod\, M & \text{if K=0} \end{cases}$$

となります。また、$f(M)=M$の時は$x\to F_x$を$\mathbb{Z}/M\mathbb{Z}$上の写像と見て繰り返し二乗法をすると$O(M\log K)$で計算できます。 $f(M)$の計算方法は、$M=\prod_k p_k^{e_k}$とすると

$$f(M)=lcm(f(p_1^{e_1}),f(p_2^{e_2}),\ldots,f(p_k^{e_k}))$$

です。また、

$$f(p^e)|p^{e-1}f(p)$$

であり、

$$f(p)= \begin{cases} 20 & \text{if p=5}\\ p-1 & \text{if p=1,4 mod 5}\\ 2(p+1) & \text{if p=2,3 mod 5} \end{cases}$$

となります。 $f(p^e)=p^{e-1}f(p)$として計算しても正しく答えを求められます。