You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一个 $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$ 为单位矩阵 $I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$。

题目描述

给定 $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$ 取模。

2 1
1 1
1 1

1 1
1 1

提示

【数据范围】

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