642. 线性递推式

【问题描述】

动态规划 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$

对于 100% 的数据：$N\le K\le 10^2,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] \]