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的值。

【数据规模】 对于50%的数据，N≤K≤10^6； 对于100%的数据，1＜N≤10；N≤K≤10^8；1≤Ai,Fi≤10^4