矩阵多项式

题目描述

$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$

$A^0 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ A^1 = \begin{bmatrix} 1 & 2 & 3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \\ A^2 = \begin{bmatrix} 3 & 5 & 3 \\ 1 & 2 & 3 \\ 1 & 0 & 0 \end{bmatrix} \\ A^0+2A^1+3A^2 = \begin{bmatrix} 12&19 &15 \\ 5 & 7 & 9 \\ 3 & 2 & 1 \end{bmatrix} \\$

详情

题目描述