動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：
一個 N 階線性遞推式是這樣的式子：
也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。
例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。
LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。
【輸入文件】
第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。
第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。
第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。
【輸出文件】
只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。
