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

Input 1

2 10
1 0
0 1

Output 1

1 0
0 1

Explanation 1

The matrix never changes, it is the identity matrix.

Input 2

1 10
2

Output 2

1024

Explanation 2

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

Input 3

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

Output 3

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

Explanation 3

Remember to modulo!