Pondo Matrices

Problem Statement

Pondo has a square matrix consisting of only positive integers $A$ of length $n$ and an integer $k$, he would like to know what $A^k$ is. Since the individual entries of the matrix can get very large, output each of the entries modulo $10^9+7$.

Input Format

Your first line will contain two integers $n$ and $k$, space-separated. Your next $n$ lines will contain $n$ space-separated positive integers each, the $i^{th}$ of which represents the $i^{th}$ row of the matrix.

Output Format

You should output $A^k$ one row per line, space-separated integers for each row and all integers modulo $10^9+7$.

Constraints

• $1 \leq n \leq 10$
• $1 \leq A_{ij}, k \leq 10^9$

Sample Cases

2 10
1 0
0 1

1 0
0 1

Explanation 1

The matrix never changes, it is the identity matrix.

1 10
2

1024

Explanation 2

The output should simply be $2^{10}$.

4 1000000000
1 2 3 4
2 3 4 5
4 5 6 7
7 8 9 10

113333985 65337891 17341797 969345710
998061335 882788678 767516021 652243364
767516021 517690238 267864455 18038672
421698050 970042585 518387113 66731641

Explanation 3

Remember to modulo!