题目描述

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

$$h_n = a1 \times h{n-1} + a2 \times h{n-2} + ... + ak \times h{n-k}$$

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

输入格式

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

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

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

输出格式

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

样例

input

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

output

73

数据范围与提示

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