累乘矩阵

博弈分析完了，但Echo-0的核心加密还有一个——矩阵。不是单个数，是一堆数排成的方阵。

"矩阵？"CC问。

"对。"你说，"给定$n\times n$矩阵$A$，求$A^k$。"

"$A^k$？"

"对。"你说，"矩阵乘自己$k$次。"

"咋算？"

"快速幂。"你说，"和数的快速幂一样，只不过底数是矩阵，乘法是矩阵乘法。"

"矩阵乘法？"

"对。"你说，"$C_{ij}=\sum_k A_{ik}\times B_{kj}$。"

"复杂？"

"$O(n^3)$。"你说，"但每次乘法都是$n^3$。"

"快速幂多少次？"

"$O(\log k)$。"你说，"总复杂度$O(n^3\log k)$。"

"第47次幂。"你说，"$k=47$。"

"$\log 47\approx 6$。"你说，"6次矩阵乘法。"

"快。"

"对。"你说，"如果直接乘47次，慢多了。"

"矩阵是啥？"

"一种数据结构。"你说，"表示线性变换——旋转、缩放、投影。"

"像变形？"

"对。"你说，"像变形——矩阵作用在向量上，向量就变了。"

CC看着矩阵——像一张表，像一面墙，像某种可以变换空间的魔法。

"能变我吗？"她问。

"能。"你说，"如果把你的坐标当成向量，矩阵可以旋转你、缩放你。"

"我不想变。"

"那就不变。"你说，"矩阵只是工具，用不用看我们。"

Echo把矩阵的变换效果投射出来——一个立方体旋转、扭曲、最终复原。

"以前我被矩阵困住。"她说，"现在……我控制它了。"

"因为你在学。"CC说。

"对。"Echo说，"因为我在学。"

题目描述

给定$n\times n$矩阵$A$和正整数$k$，求$A^k$模$10^9+7$。

输入格式

第一行$n$和$k$。接下来$n$行，每行$n$个整数。

输出格式

$n$行，每行$n$个整数表示结果矩阵。

输入样例

5

输出样例

0

提示

• 矩阵快速幂：和整数快速幂类似，乘法改为矩阵乘法。
• 矩阵乘法$O(n^3)$，快速幂$O(\log k)$。
• 总复杂度$O(n^3\log k)$。