## MPOW - Power of matrix

You will be given a square matrix M and a positive integer power N. You will have to compute M raised to the power N. (that is, M multiplied with itself N times.)

### Input

First line of input is T ( number of test-cases) First line of each test-case contains two integer M , N where M is size of square matrix that we have to exponent and N is the power to which we have to exponent
Next M lines describe the input matrix. Each line contains exactly M elements corresponding to each array

### Output

Output M line corresponding to each row of resultant matrix Each line must have M integers where jth element of ith line is jth element of resultant matrix taken modulo with 1000000007 (10^9+7).

Simply , you have to print the resultant square matrix.

### Example

```Input:
2
2 3
1 0
1 1
3 3
1 0 4
1 2 2
0 4 4
```
```Output:
1 0
3 1
17 112 116
15 88 100
28 144 160
```

constraints:

1<=T<=10

1<=M<=50

1<=N<=100000

0<=each element of input matrix<=10^9

 < Previous 1 2 3 Next > adityaguptagkp: 2021-02-06 17:21:57 if anyone is here after watching the CodeNcode video do this in multiplication operator :- res[i][j] = (res[i][j] % mod + ((A[i][k] % mod) * (B[k][j] % mod) % mod)) % mod where mod = 1e9 + 7 And use long long int instead of int ratnesh123: 2021-01-10 08:47:53 i am getting TLE ,even doing in O(m^3*logn) why?? kokonut_hustle: 2020-12-02 14:52:35 - use fast exponentiation - use long long - use % mod for every + and * Last edit: 2020-12-02 15:45:36 mascoder: 2020-11-13 11:23:57 I am doing in java and I followed code ncode's video still I am stuck at test case 7, and I am using long matrix not passing it by reference. Even then :( tush_chen: 2020-11-13 07:20:33 If anyone is getting TLE even after using the modulo operator with prudence, make sure you are passing your vectors by reference and not value, took me a while to figure that out :( iamblank_99: 2020-10-06 15:45:11 if anyone is here after watching the CodeNcode video do this in multiplication operator :- res[i][j] = (res[i][j] % mod + ((A[i][k] % mod) * (B[k][j] % mod) % mod)) % mod where mod = 1e9 + 7 md__talha__007: 2020-10-02 08:27:01 Can any one help me Even using matrix exponentiation I'm getting WA and I have also seen CodeNcode ' video But WA on 6,5,4 on 3 submissions after making changes Evendoing MOD bfore printing the resultant matrix aanchal_2894: 2020-09-12 01:06:49 i am getting tle in python . i used matrix exponentiation method. Last edit: 2020-09-12 01:07:38 alamgir58: 2020-09-04 08:29:06 0.07sec && 4.7MB mdyamin: 2020-07-28 13:30:49 If you can't figure out why you are getting wa then use long long and use modular arithmetic wisely.