题面：https://www.luogu.com.cn/problem/U703133
题目从何而来？
这堆破玩意的原题是这样的：
\(T\) 组数据，设斐波那契数列 \(\{F_n\}\)，众所周知有个定理是 \(F_d|F_{nd}\)，求 \(k\pmod m\) 使得 \(kF_d\equiv F_{nd}\pmod m\)。不保证 \(F_d\) 对 \(m\) 有逆元。
\[1\leq T\leq10^5,1\leq n,d,m\leq 10^9
\]
结论1：
\[F_{a+b}=F_{a+1}F_b+F_{a}F_{b-1}
\]
可以用二元归纳法证明，至于怎么正着推我特么怎么知道。
拆一下：
\[F_{nd}=F_{(n-1)d+1}F_d+F_{(n-1)d}F_{d-1}\\
F_{(n-1)d}=F_{(n-2)d+1}F_d+F_{(n-2)d}F_{d-1}\\
则F_{nd}=(F_{(n-1)d+1}+F_{d-1}F_{(n-2)d+1})F_d+F_{d-1}^2F_{(n-2)d}
\]
以此类推
\[F_{nd}=F_d\sum_{i=0}^{n-1}F_{d-1}^iF_{(n-i-1)d+1}
\]
有点毒瘤啊
做法
所以这东西跟卷积毫无关系。
下面是我跟 gemini 老师学的，我只会推出来这个烂题但我不会做（
我们知道斐波那契递推矩阵是这样的：
\[A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\\
A^k = \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix}
\]
则
\[A^{(n-i-1)d} = \begin{pmatrix} F_{(n-i-1)d+1} & F_{(n-i-1)d} \\ F_{(n-i-1)d} & F_{(n-i-1)d-1} \end{pmatrix}
\]
那么
\[X=\sum_{i=0}^{n-1}F_{d-1}^iA^{(n-i-1)d}\\
\]
\(X_{0,0}\pmod m\)就是答案。
发挥极致的注意力：
\[A^d=\begin{pmatrix} F_{d+1} & F_d \\ F_d & F_{d-1} \end{pmatrix}=\begin{pmatrix} F_{d} & F_d \\ F_d & 0 \end{pmatrix}+\begin{pmatrix} F_{d-1} & 0 \\ 0 & F_{d-1} \end{pmatrix}=F_dA+F_{d-1}I
\]
则得到一个非常神奇的恒等式：
\[A^d-F_dI=F_dA
\]
注意到 \((x^n+y^n)=(x-y)(\sum_{i=0}^{n-1}x^iy^{n-1-i})\)，容易观察到与上面相像，代回 \(X\) 的定义式：
\[(A^d-F_dI)X=A^d-F_dI\sum_{i=0}^{n-1}F_{d-1}^iA^{(n-i-1)d}\\
F_dAX=A^n-F_{d-1}^nI
\]
根据矩阵乘法规则，\((AX)_{1,0}=X_{0,0}\times A_{0,1}+X_{0,1}\times A_{1,1}=X_{0,0}\)，又有\((A^n-F_{d-1}^nI)_{1,0}=A^n_{0,0}=F_{nd}\)。
这就推回来了：
\[X_{0,0}\equiv \frac{F_{nd}}{F_{d}} \pmod m
\]
不保证存在对 \(m\) 的逆元，那么这个怎么做呢？
结论2：
\[F_{nd} = L_d F_{(n-1)d} - (-1)^d F_{(n-2)d}，其中L_d 为第d个Lucas数，L_d = F_{d-1} + F_{d+1}
\]
\(F_d\) 是常数，设 \(U_d=\frac{F_{nd}}{F_{d}}\)，它也必然满足 \(U_{nd} = L_d U_{(n-1)d} - (-1)^d U_{(n-2)d}\)。
容易构造矩阵，注意在模 \(m\) 下 \(-(-1)^d\) 不能直接填进去，设 \(C=-(-1)^d\bmod m\)：
\[\begin{pmatrix} U_n \\ U_{n-1} \end{pmatrix} = \begin{pmatrix} L_d & C \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix}
\]
两次矩阵快速幂，时间复杂度 \(O(T(\log n+\log d))\)。
