Matrix Exponentiation

题目描述

给定 n * n 的矩阵 A, 求 A^k.

输入

输入共有 n + 1 行.

第 1 行为两个正整数 n, k.

接下来的 n 行, 每行为 n 个整数, 第 i 行第 j 个数表示 A_{i,j}.

输出

输出共有 n 行, 每行为 n 个正整数, 第 i 行第 j 个数表示 (A^k)_{i,j}.每个矩阵元素需对 10^9+7 取模, 即输出的每个数应为 [0,10^9+7) 范围内的整数.

样例

测试点1即为此样例

样例输入

5 3
-5 -10 -3 -1 -9 
8 2 10 10 -10 
-1 1 10 -5 -5 
0 1 1 6 -1 
-9 9 0 -8 -10

样例输出

999997279 1729 999998196 999997916 999998380 
999998921 999998895 999999541 999998989 844 
999999399 999999586 627 999998933 999999304 
1000000000 999999823 261 236 999999794 
999998052 999999088 700 999999349 999996378

数据范围

• n <= 100
• k <= 10^12
• A的输入数据在int范围内