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 and N, where M is size of square matrix that we have to exponent and N is the power to which we have to exponent it. The 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 (109+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 ≤ 109


hide comments
giriamit1999: 2020-07-02 10:45:39

where 1000000007 have to use ...i can't understand ....please help me

kgargdunregret: 2020-06-30 19:18:15

Why don't "int" work since we are taking modulus so value wont exceed it at any time?

kushgupta_19: 2020-06-22 18:02:17

Don't forget to use long long int.

abhisheknaiidu: 2020-05-24 16:57:46

0.04 sec and 4.7 MB

tanvir021: 2020-05-21 03:10:27

0.06 sec and 4.7 MB

omharicu: 2020-05-14 11:49:56

0.08 sec and 4.7 mb

shubham97361: 2019-08-12 15:19:14

learn matrix exponentiation.


Added by:ivar.raknahs
Date:2014-12-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own