题目描述

给定一个 $n \times n$ 的矩阵 $A$ 和两个正整数 $k$ 及 $m$，要求和 $S = A + A^2 + A^3 + \ldots + A^k$对$m$取余的结果。

输入格式

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

• 第一行输入包含三个正整数 $n$，$k$ 和 $m$。
• 接下来 $n$ 行，每行包含 $n$ 个非负整数（均不超过 $32,768$），用以描绘矩阵 $A$。

输出格式

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

样例

2 2 4
0 1
1 1

1 2
2 3

提示

数据范围

• $1 \leq n \leq 30$
• $1 \leq k \leq 10^9$
• $1 \leq m < 10^4$