According to Cayley-Hamilton theorem, the power of a $$$n$$$ times $$$n$$$ matrix can be seen as a linear recurrence have atmost n terms, so let say we have some $$$dp[n][m]$$$ which every $$$dp[i]$$$ is a $$$n$$$ times $$$1$$$ vector, and we can get $$$dp[i]$$$ from the previous $$$dp[j] (j \lt i)$$$ by multiplying a transition matrix $$$A_{n \times n}$$$, then we can manipulate Cayley-Hamilton theorem like below to get a linear recurrence of a certain entries of $$$dp[i]$$$, then brute-force the first $$$2n$$$ terms of $$$dp[i] (i \leq 2n)$$$, plug all of them into Berlekamp-Massey, and we will get the actual recurrence relation of a certain entries of $$$dp[i]$$$, finally compute the k-th term of linear recurrence in $$$O(n^2lgk)$$$ or $$$O(nlgnlgk)$$$ using FFT.

($$$A$$$ is a n times n matrix, $$$b_i$$$ is a n times 1 vector whose entry are all 0 except i-th row is 1)