P3390 [Template] Matrix Fast Exponentiation

An $m \times n$ matrix is a rectangular array of elements arranged in $m$ rows and $n$ columns. That is, $$ A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{bmatrix} \text{.} $$ In this problem, the elements $a_{i j}$ in a matrix are integers. Given matrices $A, B$ of sizes $m \times n$ and $n \times p$, respectively, their product is an $m \times p$ matrix. Denote the result by $C$, then $$ c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} $$ If the number of columns of $A$ does not equal the number of rows of $B$, the product cannot be computed. It can be verified that matrix multiplication is associative, i.e., $(A B) C = A (B C)$. An $n \times n$ matrix $A$ can be multiplied by itself to obtain another $n \times n$ matrix, denoted $A^2 = A \times A$. Furthermore, higher powers can be defined recursively as $A^k = A \times A^{k - 1}$, or $A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}$. In particular, define $A^0$ as the identity matrix $I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$.

Given an $n \times n$ matrix $A$, compute $A^k$.

The first line contains two integers $n,k$. Then follow $n$ lines, each containing $n$ integers. In row $i$, the $j$-th number denotes $A_{i,j}$.

Output $A^k$. There are $n$ lines in total, each containing $n$ numbers. The number in row $i$ and column $j$ denotes $(A^k)_{i,j}$. Each element is taken modulo $10^9+7$.

Constraints For $100\%$ of the testdata, $1 \le n \le 100$, $0 \le k \le 10^{12}$, $|A_{i,j}| \le 1000$. Translated by ChatGPT 5