2469. 矩阵的幂

【题目描述】

给定一个$n\times n$的矩阵$A$，求$A^k$，结果矩阵中的每个数对$M$取余。

【输入格式】

第一行$3$个整数$n,k,M$。

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

【输出格式】

输出共$n$行，每行$n$个整数，表示$A^k$中的每个数对$M$取余的结果。    

【样例1输入】

2 0 10000
1 2
3 4

【样例1输出】

1 0
0 1

【样例2输入】

2 3 10000
1 2
3 4

【样例2输出】

37 54
81 118

【提示】

$A^0=E$

【数据规模与约定】

对于 $10\%$ 的数据，$k=0$。

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

对于 $50\%$ 的数据，$k \leq 5000$。

对于 $100\%$ 的数据，$n \leq 30，k \leq 10^{10}，M \leq 2\times 10^{9}, |A_{i,j}|\leq 10^{18}$。