시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB299876529.148%

## 문제

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.

## 예제 입력 1

2 17 2
1 2
3 4
0 0 0


## 예제 출력 1

7 10
15 5


## 출처

• 잘못된 조건을 찾은 사람: goooora