A 公司的天气预报系统的原理如下：用一个大于等于 $0$，小于等于 $4146$ 的整数来表示这一天的天气情况，在预测未来某一天的天气情况时，要根据此前 $n$ 天的天气情况来预测，如果用 $w(i)$ 表示第 $i$ 天的天气情况（$i>n$），那么 $w_i=(a_1\times w(i-1) +a_2\times w(i-2)+\cdots+a_n\times w(i-n))\mod4147$，其中 $a_1,a_2,\cdots ,a_n$ 是已知常数。现给出前 $n$ 天的天气情况，问第 $m$ 天的天气预测结果是什么。

输入数据的第一行是两个正整数 $n$ 和 $m$，第二行有 $n$ 个非负整数，分别为 $w_n,\cdots,w_1$。第三行又有 $n$ 个非负整数，分别表示 $a_1,a_2,\ldots,a_n$。

输出一个整数，表示对第 $m$ 天的天气预测结果。

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