P050 矩阵快速幂

题目描述

给定一个 n \times n 的矩阵 A，计算 A^k \bmod m。

要求时间复杂度 O(n^3 \log k)。

输入格式

第一行三个整数 n, k, m（1 \le n \le 50，0 \le k \le 10^9，1 \le m \le 10^9）。
接下来 n 行，每行 n 个整数，表示矩阵 A。

输出格式

n \times n 的矩阵，表示 A^k \bmod m。

样例

输入:
2 3 1000
1 1
1 0

输出:
3 2
2 1