手玩远古 NOI 题。

记 $A=\begin{bmatrix}a&b\\&1\end{bmatrix}$，$B=\begin{bmatrix}c&d\\&1\end{bmatrix}$。

则

$$\binom{f_{n,k}}1=A\binom{f_{n,k-1}}1\quad(k>1)$$ $$\binom{f_{n,1}}1=B\binom{f_{n-1,m}}1\quad(n>1)$$

故化简即得

$$\binom{f_{n,m}}1=A^{m-1}B\binom{f_{n-1,m}}1\quad(n>1) $$

又

$$\binom{f_{1,m}}1=A^{m-1}\binom{f_{1,1}}1$$

因此

$$\binom{f_{n,m}}1=(A^{m-1}B)^{n-1}A^{m-1}\binom11$$

然后直接进行十进制快速幂即可。

其实本题硬要手玩可以考虑对角化、Jordan 标准型之类的，估计是可以做的。

注意，费马小定理本身在 $M_{n\times n}({\rm Z}_p)$ 上未必是成立的，但如果矩阵 $A$ 可对角化则 $A^p=A$ 总是成立。