F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4161. -- Shlw loves matrixI

4161: Shlw loves matrixI

Time Limit: 80 Sec  Memory Limit: 128 MB
Submit: 861  Solved: 408
[Submit][Status][Discuss]

Description

给定数列 {hn}前k项,其后每一项满足
hn = a1*h(n-1) + a2*h(n-2) + ... + ak*h(n-k)
其中 a1,a2...ak 为给定数列。请计算 h(n),并将结果对 1000000007 取模输出。

Input

第 1 行包含两个整数 n,k
第 2 行包含 k 个整数 a1,a2...ak
第 3 行包含 k 个整数h[0],h[1],...,h[k-1] 
n <= 10^9;k <= 2000; abs(hi)<=10^9; abs(ai)<=10^9

Output

一行一个整数 hn mod 1000000007

Sample Input

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

Sample Output

73

HINT


Source

By submittersubmitter

[Submit][Status][Discuss]

HOME Back