6175. 【模板】矩阵快速幂
时间限制：1000 MS 内存限制：512 MB
题目描述
# P3390 【模板】矩阵快速幂 ## 题目背景 一个 $m \times n$ 的**矩阵**是一个由 $m$ 行 $n$ 列元素排列成的矩形阵列。即形如  本题中认为矩阵中的元素 $a\_{i j}$ 是整数。 两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ **相乘**的结果为一个大小为 $m \times p$ 的矩阵。将结果矩阵记作 $C$，则 $ c\_{i j} = \sum\_{k = 1}^{n} a\_{i k} b\_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} $ 而如果 $A$ 的列数与 $B$ 的行数不相等，则无法进行乘法。 可以验证，矩阵乘法满足结合律，即 $(A B) C = A (B C)$。 一个大小为 $n \times n$ 的矩阵 $A$ 可以与自身进行乘法，得到的仍是大小为 $n \times n$ 的矩阵，记作 $A^2 = A \times A$。进一步地，还可以递归地定义任意高次方 $A^k = A \times A^{k - 1}$，或称 $A^k = \underbrace{A \times A \times \cdots \times A}\_{k \text{ 次}}$。 特殊地，定义 $A^0$ 为单位矩阵 。  ## 题目描述 给定 $n\times n$ 的矩阵 $A$，求 $A^k$。 ## 输入格式 第一行两个整数 $n,k$。 接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A\_{i,j}$。 ## 输出格式 输出 $A^k$ 共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k)\_{i,j}$，每个元素对 $10^9+7$ 取模。 ## 输入输出样例 #1 ### 输入 #1 ``` 2 1 1 1 1 1 ``` ### 输出 #1 ``` 1 1 1 1 ``` ## 输入输出样例 #2 ### 输入 #2 ``` 3 5 1 2 3 4 5 6 7 8 9 ``` ### 输出 #2 ``` 121824 149688 177552 275886 338985 402084 429948 528282 626616 ``` ## 说明/提示 **【数据范围】** 对于 $100\%$ 的数据，$1\le n \le 100$，$0 \le k \le 10^{12}$，$|A\_{i,j}| \le 1000$。