509006 - N阶线性递推式

【题目描述】N阶线性递推式(N)

一个N阶线性递推式是这样的式子:Fi=A0Fi-n+A1Fi-(n-1)+…+An-1Fi-1+An,也就是说,这个数列的每一项都是由它之前连续N项相加所得,其中还包括一个常数An。例如当N=2,A0=A1=1,A2=0时,这个式子就是我们熟悉的斐波那契数列。当然,作为边界条件,F0,F1…Fn-1都是已知的。 试对一个给定的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^8;1≤Ai,Fi≤10^4

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题