3. 矩阵幂之和

【题目描述】

给定一个$n\times n$的矩阵$A$和一个正整数$k$，求$S=A+A^2+A^3+\cdots+A^k$。大样例

【输入格式】

第一行三个正整数$n,k,m$。

以下$n$行，每行$n$个小于$m$的非负整数，表示矩阵$A$。

【输出格式】

$n$行，每行$n$个数，表示矩阵$S$中的每个元素$\mod m$的值。

【样例输入】

2 2 4
0 1
1 1

【样例输出】

1 2
2 3

【数据范围与约定】

对于30%的数据，$k\leq 10^5$。

对于60%的数据，$m\leq 10^8$。

对于100%的数据，$n\leq 30,k\leq 10^{10},m\leq 10^{18}$。

【来源】