题目描述

给定$n$×$n$ 矩阵 $A$和正整数$k$，求和$S=A+A^2+A^3+…+A^k$。

输入格式

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

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

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

输出格式

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

样例

2 2 4
0 1
1 1

1 2
2 3

数据范围

$1≤n≤30, 1≤k≤10^9, 1≤m<10^4$

来源

• POJ3233
• 算法竞赛进阶指南