时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出一个 \(m*m\) 的矩阵，请计算矩阵 \(B=A^n\)，其中 \(B\) 的每个元素 \(mod\ 1000007\)。

【输入格式】

　　第一行包含两个整数：\(m\) 和 \(n\)；
　　接下来的 \(m\) 行，每行 \(m\) 个整数，表示矩阵 \(A\)。

【输出格式】

　　包含 \(m\) 行 \(m\) 列，表示 \(A^n\) 每个元素 \(mod\ 1000007\) 的结果。

【输入输出样例】

　Input

2 3
1 2
3 4

　Output

37 54 
81 118 

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤m≤10\)，\(0<n≤10^9\)，输入的矩阵中每个元素都是不大于 1000 的非负整数。

【来源】

　　Mr.he