Matrix Power Series

Input

The first line contains three positive integers $n$ (n \leq 30), $k$ (k \leq 10^9), and $m$ (m < 10^4). Then follow $n$ lines, each containing $n$ non-negative integers less than $32768$, which define the elements of matrix $A$ in row-major order.

Output

Print the elements of matrix $S$ modulo $m$ in the same format as matrix $A$ is given.

Examples