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