题目描述

给你一个 $n$ 维矩阵 $A$，求 $m$ 个该矩阵的连乘结果。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行每行 $n$ 个数字，表示该矩阵。

$1\leq n \leq100$，$1 \leq m \leq 10^{18}$。 $0\leq A_{ij} \leq 10^9$。

输出格式

对每组输入，输出其运算结果。由于结果可能很大，对每个矩阵元，输出其除以 $10^9+7$ 的余数即可。

3 3
1 2 3
4 5 6
7 8 9

468 576 684 
1062 1305 1548
1656 2034 2412

3 10000
1 2 3
4 5 6
7 8 9

820213633 684124829 548036025      
879174047 976698656 74223258       
938134461 269272476 600410498

3 1000000000000000000
1 2 3
4 5 6
7 8 9

416119295 559243495 702367695
300238211 170735569 41232927
184357127 782227650 380098166