5095번 - Matrix Powers 다국어

Your task is to write a program to raise an integer matrix to a given power using modulo arithmetic. There is no back story here; at least not one that can be told. The application is too confidential (spying and military intelligence and all that) to be described in public.

For example, to raise the 2 by 2 matrix 

\[\begin{pmatrix}  1&2  \\  3&4  \end{pmatrix}\]

to the power 2 using modulo 17 arithmetic 

\[\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\times \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix}(1 \times 1 + 2 \times 3) \text{ mod } 17 & (1 \times 2 + 2 \times 4) \text{ mod } 17 \\ (3 \times 1 + 4 \times 3) \text{ mod } 17 & (3 \times 2 + 4 \times 4) \text{ mod } 17  \end{pmatrix} = \begin{pmatrix} 7 & 10 \\ 15 & 5 \end{pmatrix}\]

The input consists of a number of problems. Each problem starts with a line holding three numbers (N, M, and P) separated by single spaces. 1 ≤ N ≤ 100 is the size (N by N) of the matrix to be processed. 1 ≤ M ≤ 32000 is the modulo base and 1 ≤ P ≤ 32000 is the power to which the matrix must be raised. Following this line are N lines, each holding the n integer values of successive rows of the matrix as a series of positive integers i: 0 ≤ i < M separated by single spaces. Input is terminated by a line with three zeros.

Output for each problem consists of the N rows of the result matrix, followed by a blank line. Each row is output on a single line as a sequence of integer values separated by single spaces. It doesn’t matter that lines may be quite long – no-one will be allowed to read them anyway.