首先，考虑直接DP，显然我们需要求出两个数组：f[i][j]：走一条路，与出来是i，步数为j的方案数；g[i][j]：走若干条路，与出来是i，步数为j的方案数。

显然f可以直接通过矩阵乘法n^3m做出来，但是这样并不能通过，因此我们考虑使用特征多项式来优化，原理就是我们可以用[0,n-1]次的矩阵的线性组合来表示出n次的，然后对于n+t次的矩阵，我们只需要给等式的右边乘上这个矩阵就好了。对于这道题，如果我们枚举了一个与出来的值i，那么我们可以搞出来一个行（列）向量以及它的转置，然后给等式左边和右边乘上这个向量及转置，之后就有递推式了，形式化一点，设\(B_{n+i} = X  A^{n+i} X^{T}\)，那么有\(B_{n+i}=\sum _{j=0}^{n-1}h_{j}X A^{j+i} X^{T} = \sum _{j=0} ^{n-1} h_{j} B{j+i} \)，之后，我们可以暴力O(n^4)算出前n个矩阵，然后O(n^2m)递推剩下的。

对于特征多项式的求解，由于这道题并不是什么常系数递推，我们只能暴力求解，具体就是用定义式\(char(A) = | A - \lambda E | \)，带入不同的λ，求解行列式的值，然后高斯消元得到系数h，复杂度O(n^4+n^3)。

之后我们就能求出f了，考虑如何求g。我们可以先对第一维进行FWT，之后对第二维进行NTT，这样单次卷积的复杂度就是O(nm)了，考虑到最后的结果其实就是k次卷积之和，我们可以用等比数列求和公式转化到多项式求逆上，然后可以O(nmlogm)的复杂度得到结果。考试的时候想的是用倍增来做，不过这样需要每次都DFT回去进行取模，复杂度好像是两个log的。

然后我们只需要卡卡常数就可以过去了，对于32位的机子，只有在卡取模的常数的时候才要用long long，其他的还是全程int吧。多项式取模现算长度应该会快一点？

总的来说，考试的时候只会\(O(n^3 m + n m log^2 m logn)\)的做法，但是觉得前面的n^3m会让这个算法直接沦为最弱的暴力，于是就直接写了\(O(n^3 m + n^2 m^2)\)的，成功被subtask卡掉了。