Description

给定 $n\times n$ 的矩阵 $A$，求 $A^k$。

Input Format

第一行两个整数 $n,k$。
接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。

Output Format

输出 $A^k$

共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$，每个元素对 $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

【数据范围】

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