You are given a square matrix M and a positive integer 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 array that you have to exponent and N is the power to which you have to exponent .

Next M lines describe the input matrix. Each line contains exactly M elements separated by single space .

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

Elements of each row of resultant matrix must be separated by single space.

Conatraints

1<=T<=10

1<=M<=50

1<=N<=100000

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