基准时间限制：3

 秒 空间限制：131072 KB 分值: 40 

 

给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。

 

Input

第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9)第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)

Output

共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。

Input示例

2 31 11 1

Output示例

4 44 4 学习了矩阵乘法

  

#include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int MOD=1e9+7;typedef struct{    int m[111][111];}matrix;int n,k;matrix operator * (matrix a,matrix b){    matrix res;    LL x;    for(int i=0;i
          
           >=1;    }    return s;}int main(){    while(scanf("%d%d",&n,&k)!=EOF)    {        matrix a;        for(int i=0;i