线性递推式

Time Limit: 1s Memory Limit: 256MB Submissions: 28 Solved: 1 
Description

动态规划DP的实现形式之一是递推,因此递推在oi中十分重要。在某信息学的分支学科中,LC学会了如何求一阶线性递推数列。由于他想在正在学习主干学科,因此希望知道求出N阶线性递推数列。为此,他了解到了以下的内容:
一个N阶线性递推式是这样的式子:

也就是说,这个数列的每一项都是由他之前连续N项加权相加所得。其中还包括一个常数An。
例如,当N=2,a0=a1=1,a2=0时,这个式子就是我们熟悉的斐波那契数列。当然,作为这界条件,f0、f1…fn-1都是已知的。
LC对这如何去求这个式子一筹莫展,因此请你来帮助他。你的任务就是对于一个给定的N阶线性递推式,求出它的第K项是多少。

Input

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

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

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

Output

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

Sample Input
2 10
1 1 0
0 1
Sample Output
55
Hint

【数据范围】
对于50%的数据:N<=K<=10^6
对于100%的数据:
1<N<10
N<=K<=101^8
1<=Ai,Fi<=10^4


【提示】
例如,对于斐波那契数可以列出这个递推公式:

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