Description

Company A's weather forecasting system works as follows: it represents the weather of a day by an integer greater than or equal to $0$ and less than or equal to $4146$. To predict the weather of some future day, it uses the weather of the previous $n$ days. If we denote the weather of day $i$ by $w_i$ ($i>n$), then $w_i=(a_1\times w_{i-1}+a_2\times w_{i-2}+\cdots+a_{n}\times w_{i-n})\mod4147$, where $a_1,a_2,\cdots ,a_n$ are known constants. Given the weather of the first $n$ days, find the prediction for day $m$.

Input Format

The first line of input contains two positive integers $n$ and $m$. The second line contains $n$ non-negative integers, namely $w_n,w_{n-1},\cdots,w_1$. The third line contains $n$ non-negative integers, namely $a_1,a_2,\ldots,a_n$.

Output Format

Output a single integer, which is the predicted weather for day $m$.

2 3
4 5
6 7

59

Hint

$1\le n\le 100$, $n<m\le10^7$, $0\le a_i,w_i\le 4146$.

Time limit per test point: 1.5 seconds.

Translated by ChatGPT 5