该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个 $n\times n$ 的矩阵 $A$ 和一个正整数 $k$，求矩阵 $A$ 的 $k$ 次方对给定的整数 $m$ 取余后的矩阵。

以下是矩阵乘法的定义：

对于两个 $n\times n$ 的矩阵 $A=(a_{ij})$ 和 $B=(b_{ij})$ ，它们的乘积 $C = AB$ 也是一个 $n\times n$ 的矩阵，其中 $C$ 中的元素 $c_{ij}$ 的计算公式为：

具体来说：

矩阵 $C$ 的第 $i$ 行第 $j$ 列的元素 $c_{ij}$ 是由矩阵 $A$ 的第 $i$ 行的每个元素与矩阵 $B$ 的第 $j$ 列的对应元素相乘后求和得到的。

先固定 $i$ 和 $j$ ，对于 $k$ 从 $1$ 到 $n$ ，依次计算 $a_{ik}b_{kj}$ 的值，并将这些值累加起来，这个累加和就是 $c_{ij}$ 的值。

输入格式

第一行三个正整数 $n,m,k$，数字之间用空格隔开。

接下来 $n$ 行，每行 $n$ 个正整数，表示矩阵。

输出格式

输出 $n$ 行，每行 $n$ 个正整数，中间用空格隔开。

样例数据

3 1000 2
1 0 2
0 3 0
4 0 5

9 0 12
0 9 0
24 0 33

数据范围

对于 $20\%$ 的数据，$k=1$

对于 $50\%$ 的数据，$k=2$

对于 $80\%$ 的数据，$k \le 10$

对于 $100\%$ 的数据，$0\lt n \le 200, 0\lt k \le 1000,0\lt m \le 40000,0 \le 矩阵元素 \le 40000$