#1285. 【模板】矩阵快速幂

【模板】矩阵快速幂

题目描述

给定 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
3 5
1 2 3
4 5 6
7 8 9
121824 149688 177552
275886 338985 402084
429948 528282 626616

题目来源:洛谷 P3390