4319 - 矩阵快速幂

一个 m×nm \times n矩阵是一个由 mmnn 列元素排列成的矩形阵列。即形如

本题中认为矩阵中的元素 aija_{i j} 是整数。

两个大小分别为 m×nm \times nn×pn \times p 的矩阵 A,BA, B 相乘的结果为一个大小为 m×pm \times p 的矩阵。将结果矩阵记作 CC,则

而如果 AA 的列数与 BB 的行数不相等,则无法进行乘法。

可以验证,矩阵乘法满足结合律,即 (AB)C=A(BC)(A B) C = A (B C)

一个大小为 n×nn \times n 的矩阵 AA 可以与自身进行乘法,得到的仍是大小为 n×nn \times n 的矩阵,记作 A2=A×AA^2 = A \times A。进一步地,还可以递归地定义任意高次方 Ak=A×Ak1A^k = A \times A^{k - 1},或称 Ak=A×A××Ak 次A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}

特殊地,定义 A0A^0 为单位矩阵

输入

给定 n×nn\times n 的矩阵 AA,求 AkA^k

第一行两个整数 n,kn,k
接下来 nn 行,每行 nn 个整数,第 ii 行的第 jj 的数表示 Ai,jA_{i,j}

输出

输出 AkA^k

nn 行,每行 nn 个数,第 ii 行第 jj 个数表示 (Ak)i,j(A^k)_{i,j},每个元素对 109+710^9+7 取模。

样例

输入
复制

2 1
1 1
1 1

输出
复制

1 1
1 1

输入
复制

5 7
8 3 2 6 9 
9 7 64 13 6
31 5 9 14 8 
6 2 0 5 8 
0 7 9 6 1 

输出
复制

139738761 90444887 961464048 505067806 615955496
926327771 468237841 731062597 544208536 352208183
729198651 672906401 497688369 743241035 760448358
281557855 144803447 706334603 826034186 732677117
413674266 870952080 127382403 842214391 916366734

提示

对于 100%100\% 的数据,1n1001\le n \le 1000k10120 \le k \le 10^{12}Ai,j1000|A_{i,j}| \le 1000

来源

用户上传

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题