题目描述

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,w_{n-1},\cdots,w_1$。第三行又有 $n$ 个非负整数，分别表示 $a_1,a_2,\ldots,a_n$。

输出格式

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

2 3
4 5
6 7

59

提示

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

每个测试点时限 1.5 秒