Sum of Matrix Powers

You are given an $N \times N$ matrix $A$ and integers $K$ and $M$. Reducing every entry of $A^K$ modulo $M$ is not hard.

This task asks for something else. Define the matrix $S$ as

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

and print every entry of $S$ modulo $M$.

The first line contains $N$, $K$, and $M$ separated by spaces ($1 \le N \le 50$, $1 \le K \le 10^9$, $1 \le M \le 10^4$).

Each of the next $N$ lines contains the matrix $A$, $N$ integers per line separated by spaces ($-10^4 \le A_{ij} \le 10^4$).

Print $N$ lines. Each line holds the $N$ entries of the corresponding row of $S$ reduced modulo $M$, separated by single spaces.

Every remainder must be at least $0$ and less than $M$. Entries of $A$ can be negative, so watch the sign of the remainder.