定义矩阵变换 $\mathcal F$，它将一个$n\times n$ 的矩阵 $P$ 变成另一个 $n\times n$ 的矩阵 $Q$：对每个 $1\le i,j\le n$，$Q_{i,j}$ 的值等于矩阵 $P$ 的第 $i$ 行与第 $j$ 列的所有元素的和。

给一个 $n\times n$ 的矩阵 $P$，请计算连续对 $P$ 连续 $t$ 次应用变换 $\mathcal F$ 的结果。请输出结果对 $\mathrm{mod}$ 取模的结果。

输入格式

第一行有3个整数，$n,t,\mathrm{mod}$，分别表示矩阵的大小， $\mathcal F$ 变换的调用次数，以及模数。

接下来 $n$ 行，每行 $n$ 个 $[0,\mathrm{mod}-1]$ 中的整数，表示矩阵的元素。

输出格式

输出 $n$ 行，每行 $n$ 个 $[0,\mathrm{mod}-1]$ 的数字，表示结果。

对所有数据有 $1\le n\le 1000, 0\le t\le 10^9, 2\le \mathrm{mod}\le 10^9$

样例数据

样例 1 输入

3 2 10
1 2 3
4 5 6
7 8 9

样例 1 输出

4 3 2
1 0 9
8 7 6

样例 1 解释

1. 初始矩阵 $$ \begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{matrix} $$

2. 一次变换后： $$ \begin{matrix} 8 &1 &4\\ 7 &0 &3\\ 6 &9& 2 \end{matrix} $$

3. 两次变换后： $$ \begin{matrix} 4 &3& 2\\ 1 &0 &9\\ 8 &7 &6\\ \end{matrix} $$

子任务

子任务一(17分)： $n\le 100,t\le 100$.

子任务二(26分)： $\mathrm{mod}=2$.

子任务三(57分)： $n\le 1000,t\le 10^9,\mathrm{mod}\le 10^9$.