18 1 s 128 MB

Fast Matrix Multiplication can be applied to many areas.

Given a **r*****r** matrix **M**, and integer **n**, print **M ^{n}**.

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

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 **M _{ij}**.

For each test case, print **r** lines containing **r** integers representing **M**^{n}_{ij}.

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