常系数齐次线性递推

名字的来由大概是系数是常数，次数相同的线性递推。

形如

[a_n=sum_{i=1}^ka_{n-i}*b_i ]

现在给你(a,b)数组，求(a_n)，满足(n ge k)。

直接暴力枚举，复杂度(Theta(n*k))。

考虑每一次转移都是相同的，所以可以把(b)写到矩阵里面然后矩阵快速幂转移。

特征多项式和特征方程（自行百度）

现在我们要求的就是(b^n)，一般的矩阵快速幂复杂度(k^3logn)，所以我们需要奇技淫巧。

(b^n=phi(B)*P(B)+Q(B))，又因为(phi(B)=0)，所以(Q(B)=b^n)。

此时我们要求的就是(Q(B))，然后它是一个和(phi(B))拥有同样项数(k)的多项式，所以复杂度变成了(k^2log^2n)。

还可以进一步优化，即(Q(B))每一次长度会(*2)，但是我们可以只去前(k)位，把后面的系数补上来，这样就做完了。

于是我们推出了一些形如

[a_n=sum_{i=1}^ka_{n-i}*b_i ]

的式子的快一点点的求法！

直接按照上文的方法做就行了。但是由于(BZOJ)机子太快了我(TLE(80s))了。

如果是(CJ)的同学可以去(MOJ)提交（当然如果你像( exttt{hyj})一样快就没必要了）