#6017. Shlw loves matrix I

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

给定数列 \{h_n\} k 项,其后每一项满足

h_n = a_1 \times h_{n-1} + a_2 \times h_{n-2} + ... + a_k \times h_{n-k}

其中 a_1,a_2\cdots a_k 为给定数列。请计算 h(n) ,并将结果对 1000000007 取模输出。

输入格式

第一行输入两个正整数 n,k

第二行输入 k 个正整数表示 a_1,\dots, a_k

第三行输入 k 个正整数表示 h_0,\cdots ,h_{k-1}

输出格式

一行输出一个数,表示 h_n 1000000007 取模的结果。

样例

样例输入

6 4
3 -1 0 4
-2 3 1 5

样例输出

73

数据范围与提示

k\leq 2000,n\leq 10^9