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。

天津省选