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
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.

kishlay1105: 2020-07-27 08:49:39

->If you are not able to build logic , see code Ncode video on matrix exponentiation.
->use modulo operators correctly
->use long long
->O(m^3 logn ) time will do the work

Last edit: 2020-07-27 08:50:12
fuadul_hasan: 2020-07-16 09:50:28

after 4 days of thinking and getting lot of wa finally i come with a solution and it's accepted. codeNcode help a lot for this problem. but it's easy to think Matrix struct for this problem. its make sense to me.

Last edit: 2020-07-16 09:51:12
amb_2020: 2020-07-09 21:44:59

I have followed all the suggestions from the comments but still I am getting WA
Please help

Last edit: 2020-07-09 21:45:26
coding_sourabh: 2020-07-08 14:02:18

remember to use mod correctly gave me many WA.


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