Linear Recurrence RNG

Time limit15sMemory limit512 MB

Summary

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

Level: Hard8 of 10
Topics: Math, Divide and conquer, Number theory
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
3 5
1 2 3
4 5 6
```
Expected output
```
139
```
Example 2
Input
```
1 1
7
5
```
Expected output
```
7
```
Example 3
Input
```
2 10
1 1
1 1
```
Expected output
```
55
```