luogu#P3873. [TJOI2010] 天气预报

    ID: 7901 远端评测题 1500ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>构造线性递推递推式递推各省省选2010天津

[TJOI2010] 天气预报

题目描述

A 公司的天气预报系统的原理如下:用一个大于等于 00,小于等于 41464146 的整数来表示这一天的天气情况,在预测未来某一天的天气情况时,要根据此前 nn 天的天气情况来预测,如果用 wiw_i 表示第 ii 天的天气情况(i>ni>n),那么 $w_i=(a_1\times w_{i-1}+a_2\times w_{i-2}+\cdots+a_{n}\times w_{i-n})\mod4147$,其中 a1,a2,,ana_1,a_2,\cdots ,a_n 是已知常数。现给出前 nn 天的天气情况,问第 mm 天的天气预测结果是什么。

输入格式

输入数据的第一行是两个正整数 nnmm,第二行有 nn 个非负整数,分别为 wn,wn1,,w1w_n,w_{n-1},\cdots,w_1。第三行又有 nn 个非负整数,分别表示 a1,a2,,ana_1,a_2,\ldots,a_n

输出格式

输出一个整数,表示对第 mm 天的天气预测结果。

2 3
4 5
6 7

59

提示

1n1001\le n\le 100n<m107n<m\le10^70ai,wi41460\le a_i,w_i\le 4146

每个测试点时限 1.5 秒