矩阵多项式

题号：NC217326
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$A$ 是一个 $n\times n$ 的正方形矩阵， $b_1,b_2,\dots b_m$ 是给定的 $m$ 个非负整数。

请求出
$\sum_{i=0}^m b_iA^i$

矩阵 $A$ 具有如下形式

$\begin{bmatrix} a_1 & a_2 & \dots & a_{n-1} & a_n \\ 1 & & & & 0 \\ & 1 & & & 0 \\ & & \ddots & & \vdots \\ & & & 1 & 0 \end{bmatrix}$

说明：没写数字的地方都是0。

题目中给定的所有数字都是小于 $(10^9+7)$ 的非负整数。你输出的结果中的每个整数也只需要保留其除以 $(10^9+7)$ 的余数(非负)。

数据规模： $1 \leq n \leq 100, 1 \leq m \leq 10^6$

第一行有两个空格隔开的整数。
第二行是个空格隔开的整数。
第三行是个空格隔开的整数。

输出行列，表示所求的答案。

示例1

复制

3 2
1 2 3
1 2 3

复制

12 19 15
5 7 9
3 2 1

样例解释