Matrix Powers

Write a program that raises an integer matrix to a given power, performing every operation with modulo arithmetic. That is, every entry obtained during the computation is kept as its remainder modulo $M$.

When two matrices are multiplied, each entry of the product is the sum of the pairwise products of the corresponding row and column, taken modulo $M$. For example, modulo $17$,

$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \times \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix} (1\cdot1 + 2\cdot3) \bmod 17 & (1\cdot2 + 2\cdot4) \bmod 17 \\ (3\cdot1 + 4\cdot3) \bmod 17 & (3\cdot2 + 4\cdot4) \bmod 17 \end{pmatrix} = \begin{pmatrix} 7 & 10 \\ 15 & 5 \end{pmatrix}$

so raising the matrix above to the power $2$ modulo $17$ yields the matrix on the right.

The input consists of several datasets. The first line of each dataset contains three integers $N$, $M$, and $P$ separated by single spaces.

• $1 \le N \le 100$: the size ($N \times N$) of the matrix
• $1 \le M \le 32000$: the modulo base
• $1 \le P \le 32000$: the power to which the matrix is raised

The following $N$ lines each hold one row of the matrix as $N$ integers $i$ with $0 \le i < M$, separated by single spaces.

The input is terminated by a line containing three zeros (0 0 0), which must not be processed.

For each dataset, output the $N$ rows of the resulting matrix. Print each row on its own line with the values separated by single spaces.

Separate the outputs of consecutive datasets with a single blank line. Do not print a blank line after the last dataset.