#1621 FastMatrixMultiplication

18  1 s   128 MB  

Description

Fast Matrix Multiplication can be applied to many areas.

Given a r*r matrix M, and integer n, print Mn.

Elements of the result could be very large, so please print each element modular 1,000,000,007.

 

Input

The first line of the input gives the number of test cases, T (1 <= T <= 200).

Each test case starts with a line consists of two integers r and n. r will be between 1 and 30, inclusive, and n will be between 0 and 1,000,000,000, inclusive.

Next r lines will each contain r numbers, which will be between 0 and 1,000,000,006, inclusive. j-th element of i-th line represent Mij.

 

 

 

Output

For each test case, print r lines containing r integers representing Mnij.

 

 

 

Sample Input

Sample Output

2
3 2
0 0 1
0 1 0
1 0 0
2 40
2 2
2 2
1 0 0
0 1 0
0 0 1
248320570 248320570
248320570 248320570