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


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

hide comments
2023-10-07 15:20:31
Is anyone getting TLE with python?
2023-02-11 19:21:36
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
use #define mod 1000000007 and instead of int use long long int
2022-06-24 17:58:22
If anyone is having a problem with MOD, please check the addition and multiplication property of MOD.
Use long long for 1000000007 and for 2D vector/array as well!
2022-01-25 06:00:59
may I know Why we have to use the mod for each element in the matrix.
2021-12-04 21:58:33
make sure to take mod during addition of elements in multiplication :)
2021-07-13 12:19:21
result[i][j]=(result[i][j]%mod+(I[i][k]%mod*A[k][j]%mod)%mod)%mod;
use this for modular arithematics
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
2021-01-10 08:47:53
i am getting TLE ,even doing in O(m^3*logn) why??
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
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 :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.