线性递推式

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 recursion.in 输出文件 recursion.out
【问题描述】
动态规划 DP 的实现形式之一是递推，因此递推在 OI 中十分重要。在某信息学的分支学科中， LC 学会了如何求一阶线性递推数列。由于他现在正在学习主干学科，因此希望知道求出 N 阶线性递推数列。为此，他了解到了以下的内容：
一个 N 阶线性递推式是这样的式子：
\[ f_i=a_0f_{i-n}+a_1f_{i-(n-1)}+\cdots+a_{n-1}f_{i-1}+a_n \]
也就是说，这个数列的每一项都是由他之前连续 $N$ 项加权相加所得。其中还包括一个常数 $a_n$ 。
例如，当 $N=2$, $a_0=a_1=1$, $a_2=0$ 时，这个式子就是我们熟悉的斐波那契数列。当然，作为这界条件， $f_0, f_1,...,f_{n-1}$ 都是已知的。
LC 对这如何去求这个式子一筹莫展，因此请你来帮助他。你的任务就是对于一个给定的 $N$ 阶线性递推式，求出它的第 $K$ 项是多少。
【输入文件】
第一行两个整数： N ， K ，其中 N 表示这个式子是 N 阶线性递推式， K 表示你需要求得那一项。
第二行有 N+1 个整数： $A_0, A_1,…, A_n$ ，表示这个递推式的系数。
第三行有 N 个整数： $F_0, F_1, ...,  F_{n-1}$ ，表示数列的初始值。
【输出文件】
只有一行，其中只有一个整数，表示这个数列第 K 项的值。由于数据较大，你只需输出结果 mod 9973 的值。
【样例输入】
2 10
1 1 0
0 1
【样例输出】
55
【数据范围】
对于 50% 的数据： $N \le K\le 10^6$
对于 100% 的数据：
 $N\le K\le 10^8$
$1\le A_i , F_i\le 10^4$
【提示】
矩阵(Matrix)是一个n*m（n行m列）的数组。例如[0 1]就是一个1*2的矩阵。
矩阵乘法这样定义：
    如果$\boldsymbol{A}=n\times m$，$\boldsymbol{B}=m\times t$，设矩阵$\boldsymbol{C}=\boldsymbol{A}\times\boldsymbol{B}$，则$c_{i,j}=\sum a_{i,k}\cdot b_{k,j}$，其中$\boldsymbol{C}=n\times t$。
例如，对于斐波那契数可以列出这个递推公式：

\[ [f_i\quad f_{i+1}] = [f_{i-1}\quad f_i] \times \left[\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right] \]