题目描述

你们做过超大斐波那契数列了，但是斐波那契数列只是前两项之和（两项递推式），太特殊了。现在来个一般的。

给你一个两个整数 $n$ 和 $m$，求 $m$ 项递推式的第 $n$ 项，即：

$a_n=a_{n-1}*k_1+a_{n-2}*k_2+...+a_{n-m}*k_m$

由于结果很大，请输出该结果除以 $10^9+7$ 的余数。

输入格式

第一行两个整数 $n$ 和 $m$，意义如前所述。$1≤n≤10^{18}$，$1≤m≤100$。

接下来第一行有 $m$ 个数字，表示该序列的前 $m$ 项 $a_1 \cdots a_m$。数据不超过 $10^9$。

再下来一行也有 $m$ 个数字，分别表示系数 $k_1 \cdots k_m$。数据不超过 $10^6$。

输出格式

对每组输入，输出其运算结果。

10 3
3 2 1
3 4 5

124343

前十项：$3\ 2\ 1\ 26\ 92\ 385\ 1653\ 6959\ 29414\ 124343$

100000000 4
1 2 3 4
3 5 7 9

268174022