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

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

两个大小分别为 m \times n 和 n \times p 的矩阵 A, B 相乘的结果为一个大小为 m \times p 的矩阵。将结果矩阵记作 C，则

而如果 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 取模。

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

luogu