题目描述

给定 $\red{n\times n}$ 矩阵 $\red A$ 和正整数 $\red k$ ，求和 $\red{S=A+A^2 +A^3+…+A^k}$。

输入格式

输入只包含一个测试用例。

第一行输入包含三个正整数 $\red n$ ，$\red k$ 和 $\red m$。

接下来 $\red n$ 行，每行包含 $\red n$ 个非负整数（均不超过 $\red{32}$ , $\red{768}$），用以描绘矩阵 $\red A$。

输出格式

按与描述矩阵 $\red A$ 相同的方式，输出将 $\red S$ 中所有元素对 $\red m$ 取模后得到的矩阵。

样例

输入样例

2 2 4
0 1
1 1

输出样例

1 2
2 3

提示

$\red{1\le n\le 30}$,

$\red{1\le k\le 10^9}$,

$\red{1\le m<10^4}$