#6017. Shlw loves matrix I

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

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

$$h_n = a_1 \times h_{n-1} + a_2 \times h_{n-2} + ... + a_k \times h_{n-k}$$

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

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

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

第三行输入 $k$ 个正整数表示 $h_0,\cdots ,h_{k-1}$

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

输入

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

输出

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