Background

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}$.

Problem Description

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

Input Format

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 Format

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$.

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

Hint

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