题目描述

小红在学习线性代数时，遇到了一个问题：给定一个 $n \times n$ 的方阵 $A$，她需要计算 $A$ 的 $k$ 次幂，即 $A^k$。矩阵乘法满足结合律，因此可以利用快速幂的思想在 $O(n^3 \log k)$ 的时间内完成计算。

定义 $A^0$ 为单位矩阵，即主对角线全为 $1$、其余位置全为 $0$ 的矩阵。

输入格式

第一行两个整数 $n, k$。

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

输出格式

输出 $A^k$，共 $n$ 行，每行 $n$ 个数。每个元素对 $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

提示

数据范围

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