선형 점화식 난수 생성기

로또 자동 제출 프로그램에 넣을 난수 생성기(RNG)를 만든다. 이 생성기는 다음 선형 점화식으로 수열 $A$를 만든다.

$A_i = (A_{i-1} C_1 + A_{i-2} C_2 + \cdots + A_{i-k} C_k) \bmod 104857601 \qquad (i > k)$

$k$와 $N$, 초기항 $A_1, A_2, \ldots, A_k$, 계수 $C_1, C_2, \ldots, C_k$가 주어질 때 $A_N$을 구하는 프로그램을 작성하시오.

첫째 줄에 $k$와 $N$이 공백으로 구분되어 주어진다. ($1 \le k \le 30000$, $1 \le N \le 10^{18}$)

둘째 줄에 $A_1, A_2, \ldots, A_k$가 공백으로 구분되어 주어진다.

셋째 줄에 $C_1, C_2, \ldots, C_k$가 공백으로 구분되어 주어진다. ($0 \le A_i, C_i < 104857601$)

첫째 줄에 $A_N$을 출력한다. $A_N$은 항상 104857601보다 작다.