시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 98 9 3 25.000%

문제

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. 2 <= 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 a blank line, followed by the N rows of the result matrix. 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.

예제 입력

2 17 2
1 2
3 4
0 0 0

예제 출력


7 10
15 5

힌트