测试数据来自 FtOJ/1008

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\) 取模。

Sample 1

Input

2 1
1 1
1 1

Output

1 1
1 1

Limitation

【数据范围】

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

1s, 1024KiB for each test case.