题目描述

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

73

数据范围与提示

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