Linear Recurrence RNG

Given the first k terms and coefficients of a linear recurrence and a huge index N, compute the N-th term modulo 104857601.

Hard8MathDivide and conquerNumber theoryNo attempts yetTime limit15sMemory limit512 MB

Description

Examples3

Problem

You are writing a random number generator (RNG) for a lottery auto-submit program. The generator builds a sequence $A$ from the linear recurrence below.

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

Given $k$ and $N$ , the initial terms $A_1, A_2, \ldots, A_k$ , and the coefficients $C_1, C_2, \ldots, C_k$ , write a program that computes $A_N$ .

Input

The first line contains $k$ and $N$ , separated by a space. ( $1 \le k \le 30000$ , $1 \le N \le 10^{18}$ )

The second line contains $A_1, A_2, \ldots, A_k$ , separated by spaces.

The third line contains $C_1, C_2, \ldots, C_k$ , separated by spaces. ( $0 \le A_i, C_i < 104857601$ )

Output

Print $A_N$ on the first line. $A_N$ is always smaller than 104857601.