/ FtOJ / 题库 /

「模板」矩阵快速幂

「模板」矩阵快速幂

暂无测试数据。

Description

给定 \(n\times n\) 的矩阵 \(A\) ,求 \(A^k\) 。

Format

Input

第一行两个整数 \(n,k\) 接下来 \(n\) 行,每行 \(n\) 个整数,第 \(i\) 行的第 \(j\) 的数表示 \(A_{i,j}\)。

Output

输出 \(A^k\)

共 \(n\) 行,每行 \(n\) 个数,第 \(i\) 行第 \(j\) 个数表示 \((A^k)_{i,j}\),每个元素对 \(10^9+7\) 取模。

Sample 1

Input

2 1
1 1
1 1

Output

1 1
1 1

Limitation

Data

对于 \(100\%\) 的数据:\(1\le n \le 100\) ,\(0 \le k \le 10^{12}\), \(|A_{i,j}| \le 1000\)

Time and Space

1s, 125MB.

Source

update by TNT

信息

ID
1008
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者