一开始想的是直接枚举序列统计答案，有点愚蠢了。

这$k$很小，$n$又很大，且进行的过程有周期性，所以考虑矩阵加速。递推式的转移项因为$k$小，所以很少，接下来就是分类型讨论。