Matrix Exponentiation

Given a square matrix \(M\) and a nonnegative integer exponent \(n\), compute \(M^n\) efficiently using fast exponentiation. Each element of the resulting matrix should be taken modulo \(10^9+7\). The problem guarantees that the matrix is of size \(k \times k\), and the operations must be performed modulo \(10^9+7\).

inputFormat

The first line contains two integers \(k\) and \(n\) where \(k\) is the dimension of the square matrix and \(n\) is the exponent. Each of the following \(k\) lines contains \(k\) space-separated integers representing the elements of matrix \(M\).

outputFormat

Output the matrix \(M^n\) modulo \(10^9+7\). Print \(k\) lines each containing \(k\) space-separated integers.

sample

2 2
1 1
1 0

2 1
1 1