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