破译天码

矩阵累乘完了，但Echo-0的最高级加密是天码——不是普通的密码，是天赋的密码。

"天码？"CC问。

"对。"你说，"一个线性递推，$f_n=c_1f_{n-1}+c_2f_{n-2}+\dots+c_kf_{n-k}$。"

"递推？"

"对。"你说，"给定前$k$项和系数，求第$n$项。"

"$n$很大？"

"对。"你说，"$n$可以达到$10^{18}$。"

"咋算？"

"矩阵快速幂。"你说，"把$k$阶递推写成$k\times k$矩阵，然后用快速幂。"

"矩阵长啥样？"

"第一行是系数$c_1$到$c_k$。"你说，"下面是一个移位矩阵——把$f_{n-1}$到$f_{n-k}$往下移一位。"

"第47项。"你说，"$n=47$，$k=3$。"

"矩阵$3\times 3$。"你说，"快速幂$\log 47\approx 6$次乘法。"

"快。"

"对。"你说，"不管$n$多大，都是对数时间。"

"天码是啥？"

"Echo-0用天码来生成伪随机数。"Echo说，"序列看起来随机，但实际上是确定的。"

"确定？"

"对。"你说，"知道前$k$项，就能预测后面所有项。"

"那还叫密码？"

"因为$k$很大，序列周期很长。"Echo说，"看起来随机，实际上是结构。"

CC看着递推公式——像一条链，像一条河，像某种从源头一直流下来的东西。

"源头在哪？"她问。

"前$k$项。"你说，"那是种子。"

"种子？"

"对。"你说，"种子决定了整个序列。"

"像命运？"

"对。"你说，"像命运——起点定了，后面的路就定了。"

Echo把天码的序列投射出来——像星空，像代码，像某种既有序又混乱的美。

"以前我觉得天码是锁。"她说，"现在觉得……是钥匙。"

"因为你能读它了。"你说。

"对。"她说，"因为我能读它了。

题目描述

给定$k$阶线性递推$f_n=\sum_{i=1}^k c_i f_{n-i}$，前$k$项，求第$n$项模$10^9+7$。

输入格式

第一行$k$和$n$。第二行$k$个系数$c_i$。第三行$k$个初始值$f_0$到$f_{k-1}$。

输出格式

$f_n\bmod (10^9+7)$。

输入样例

5

输出样例

5

提示

• 构建$k\times k$转移矩阵。
• 矩阵快速幂$O(k^3\log n)$。
• $k$较小时可用此算法。