행렬 거듭제곱의 합

$N \times N$ 행렬 $A$와 정수 $K$, $M$이 주어진다. $A^K$의 각 원소를 $M$으로 나눈 나머지를 구하는 것은 어렵지 않다.

이번에는 조금 다른 값을 구한다. 행렬 $S$를

$S = A + A^2 + A^3 + \cdots + A^K$

로 정의할 때, $S$의 각 원소를 $M$으로 나눈 나머지를 출력한다.

첫째 줄에 $N$, $K$, $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 50$, $1 \le K \le 10^9$, $1 \le M \le 10^4$)

다음 $N$개 줄에 행렬 $A$가 주어진다. 각 줄에는 $N$개의 정수가 공백으로 구분되어 있다. ($-10^4 \le A_{ij} \le 10^4$)

$N$개 줄에 걸쳐 행렬 $S$의 각 원소를 $M$으로 나눈 나머지를 출력한다. 각 줄에는 $N$개의 값을 공백 하나로 구분해 출력한다.

나머지는 항상 $0$ 이상 $M$ 미만이어야 한다. $A$의 원소가 음수일 수 있으므로 나머지의 부호에 주의한다.