Problem1149--#6017. Shlw loves matrix I

1149: #6017. Shlw loves matrix I

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

给定数列 {hn}\{h_n\}{hn}kkk 项,其后每一项满足

hn=a1×hn−1+a2×hn−2+...+ak×hn−kh_n = a_1 \times h_{n-1} + a_2 \times h_{n-2} + ... + a_k \times h_{n-k}hn=a1×hn1+a2×hn2+...+ak×hnk

其中 a1,a2⋯aka_1,a_2\cdots a_ka1,a2ak 为给定数列。请计算 h(n) h(n)h(n),并将结果对 10000000071000000007 1000000007 取模输出。

输入格式

第一行输入两个正整数 n,kn,kn,k

第二行输入 kkk 个正整数表示 a1,,ak

第三行输入 kkk 个正整数表示 h1,⋯,hkh_1,\cdots ,h_kh1,,hk

输出格式

一行输出一个数,表示 hnh_nhn100000000710000000071000000007 取模的结果。

样例

样例输入

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

样例输出

73

数据范围与提示

k≤2000,n≤109k\leq 2000,n\leq 10^9k2000,n109

Source/Category