P1381 - #6017. Shlw loves matrix I

Memory Limit：256 MB Time Limit：2.000 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

给定数列 ${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}

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

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

第二行输入 $k$ 个正整数表示 $a_{1}, \dots, a_{k}$

第三行输入 $k$ 个正整数表示 $h1,⋯,hkh_1,\cdots ,h_k$

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

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

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

1381: #6017. Shlw loves matrix I