8161: BZOJ4161:Shlw loves matrixI

Memory Limit:128 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定数列 {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

加入题单

上一题 下一题 算法标签: