蒟蒻自己跟自己的暴力打对拍测出来一个答案参数,然后就过了。。。
但是我不知道为啥能对。

根据题目，搞一个奇数列和偶数列前缀和，因为奇数列和偶数列的转移不同，所以我把两个转移矩阵合成一个，再转移 $\frac{m}{2}$ 次，即可；

但是前缀和转移显然不能直接到 $m$ 列，而是 $m-1$ 列，最后把两个用前缀和相加即可得到答案。

但是我的代码直接转移到 $m$ 列，再手动相加，竟然能对？？？？？？？？？？

代码

求助！！！！