Shlw loves matrix I
题目描述
给定整数序列的前 k 项 h0,h1,…,hk−1,以及系数 a1,a2,…,ak。对于每个 j≥k,有
hj=i=1∑kaihj−i.
求 hn 对 109+7 取模后的值。
输入格式
第一行两个整数 n,k(1≤n≤109,1≤k≤2000)。
第二行 k 个整数 a1,a2,…,ak。第三行 k 个整数 h0,h1,…,hk−1。系数和初值的绝对值均不超过 109。
输出格式
输出一行一个整数,表示 hn 对 109+7 的非负余数。
样例 #1
样例输入 #1
6 4
3 -1 0 4
-2 3 1 5
样例输出 #1
73
样例说明
给定的初值依次是 h0=−2,h1=3,h2=1,h3=5,递推得到 h4=6、h5=25、h6=73。