Matrix Exponentiation

Given an n × n matrix \(A\) and an integer \(k\), compute \(A^k\). The matrix exponentiation is defined as:

\[ A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ times}} \]

You are required to output the resulting matrix where each element is computed using standard arithmetic.

inputFormat

The first line of input contains two integers \(n\) and \(k\), where \(n\) is the size of the matrix and \(k\) is the exponent.

The next \(n\) lines each contain \(n\) space-separated integers representing the matrix \(A\).

outputFormat

Output the matrix \(A^k\), with each of the \(n\) lines containing \(n\) space-separated integers.

sample

2 2
1 2
3 4

7 10
15 22