1381: #6017. Shlw loves matrix I

Memory Limit:256 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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