题目描述

给定数列 $\{h_n\}$ 前 $k$ 项，其后每一项满足 $h_n=\sum_{i=1}^k a_i·h_{n-i}$，其中 $a_{1\cdots k}$ 为给定数列。

请计算 $h_n$，并将结果对 $10^9+7$ 取模输出。

输入格式

第一行两个整数 $n,k$。

第二行 $k$ 个整数 $a_{1\cdots k}$。

第三行 $k$ 个整数 $h_{1\cdots k}$。

输出格式

一行一个整数，表示 $h_n$ 对 $10^9+7$ 取模后的值。

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

73

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^9$，$1\leq k\leq 2\times 10^3$，$|h_i|,|a_i|\leq 10^9$。