#4161. Shlw loves matrixI

题目描述

给定数列 {hn}前k项，其后每一项满足

hn = a1h(n-1) + a2h(n-2) + ... + ak*h(n-k)

其中 a1,a2...ak 为给定数列。请计算 h(n)，并将结果对 1000000007 取模输出。

输入格式

第 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

输出格式

一行一个整数 hn mod 1000000007

样例

样例输入

6 4  

3 -1 0 4  

-2 3 1 5

样例输出

73

数据范围与提示