线性递推式(recursion)

【问题描述】

动态规划DP的实现形式之一是递推，因此递推在oi中十分重要。在某信息学的分支学科中，LC学会了如何求一阶线性递推数列。

由于他想在正在学习主干学科，因此希望知道求出N阶线性递推数列。为此，他了解到了以下的内容：

一个N阶线性递推式是这样的式子：

也就是说，这个数列的每一项都是由他之前连续N项加权相加所得。其中还包括一个常数An。

例如，当$N=2，a0=a1=1，a2=0$时，这个式子就是我们熟悉的斐波那契数列。当然，作为这界条件，$f0、f1…fn-1$都是已知的。

LC对这如何去求这个式子一筹莫展，因此请你来帮助他。你的任务就是对于一个给定的N阶线性递推式，求出它的第K项是多少。

【输入文件】

第一行两个整数：$N，K$，其中N表示这个式子是N阶线性递推式，K表示你需要求得那一项。

第二行有N+1个整数：$A0,A1,…，An$，表示这个递推式的系数。

第三行有N个整数：$F0，F1，….，Fn-1$，表示数列的初始值。

【输出文件】

只有一行，其中只有一个整数，表示这个数列第K项的值。由于数据较大，你只需输出结果 mod 9973的值。

【样例输入】

2 10

1 1 0

0 1

【样例输出】

55

【数据范围】

对于50%的数据：$N<=K<=10^6$

对于100%的数据：

1<N<10

N<=K<=10^18

1<=Ai，Fi<=10^4

【提示】

例如，对于斐波那契数可以列出这个递推公式：

$$[f_i \ \ f_{i+1}]=[f_{i-1}\ \ f_i]*\begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}$$

矩阵乘法不满足交换律，但满足结合律。