2526: #6017. Shlw loves matrix I

给定数列 {hn}\{h_n\}{h​n​​} 前 $k$ 项，其后每一项满足

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}h​n​​=a​1​​×h​n−1​​+a​2​​×h​n−2​​+...+a​k​​×h​n−k​​

其中 a1,a2⋯aka_1,a_2\cdots a_ka​1​​,a​2​​⋯a​k​​ 为给定数列。请计算 $h(n)$，并将结果对 $1000000007$ 取模输出。

输入格式

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

第二行输入 $k$ 个正整数表示 $a_1,\dots ,a_k$

第三行输入 $k$ 个正整数表示 h1,⋯,hkh_1,\cdots ,h_kh​1​​,⋯,h​k​​

输出格式

一行输出一个数，表示 hnh_nh​n​​ 对 $1000000007$ 取模的结果。

样例

样例输入

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

样例输出

73

数据范围与提示

k≤2000,n≤109k\leq 2000,n\leq 10^9k≤2000,n≤10​9​​