Shlw loves matrixI
时间限制：80s 空间限制：128MB
题目描述
给定数列 {hn}前k项，其后每一项满足
hn = a1*h(n-1) + a2*h(n-2) + ... + ak*h(n-k)
其中 a1,a2...ak 为给定数列。请计算 h(n)，并将结果对 1000000007 取模输出。
输入格式
第 1 行包含两个整数 n,k
第 2 行包含 k 个整数 a1,a2...ak
第 3 行包含 k 个整数 h1,h2...hk
输出格式
一行一个整数 hn mod 1000000007
样例输入
6 4 3 -1 0 4 -2 3 1 5
样例输出
73
提示
对于 100% 数据，满足 n <= 10^9;k <= 2000; abs(hi)<=10^9; abs(ai)<=10^9
题目来源
By submittersubmitter