You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

矩阵快速幂

Description

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

Format

Input

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

Output

输出 $A^k$

共 $n$ 行，每行 $n$ 个数，第$i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$​，每个元素对 $10^9+7$ 取模。

Samples

2 1
1 1
1 1

1 1
1 1

Limitation

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