首先這題要用矩陣快速冪，矩陣快速冪裡會有的東西是 $\color{black}{ans = ans\times mat}\ $ 和 $\color{black}{mat = mat\times mat}\ $，其中 $\color{black}{ans}\ $ 為欲求的矩陣，$\color{black}{mat}\ $ 則是一個 $\color{black}{2^i}\ $ 次的矩陣，如果直接運算，複雜度會是 $\color{black}{O(t\times n^3log(k))}\ $，套在這一題會 $\color{black}{\text{TLE}}\ $。

$\color{black}{mat}\ $ 其實在每次運算的時候值都是固定的，所以我們其實可以預處理好，就不用每次都乘一遍。那要如何改善 $\color{black}{ans = ans\times mat}\ $ 呢？可以發現 $\color{black}{ans}\ $ 不一定要是一個 $\color{black}{n\times n}\ $ 的矩陣，可以是一個 $\color{black}{1\times n}\ $ 的矩陣，這樣乘法就從 $\color{black}{n^3}\ $ 變成 $\color{black}{n^2}\ $ 了。於是預處理的複雜度加上快速冪的複雜度，最終就是 $\color{black}{O(n^4log(C)+t\times n^2log(k))}\ $。