题目描述

Givena $n×n$ matrix $A$ and apositive integer $k$，find the sum $S=A+A^2 +A^3 +...+A^k$.

输入格式

The input contains exactly one test case. The first line of input contains three positive integers $n$ ($n \le 30$), $k$ ($k \le 10^9$) and $m$ ($m < 10^4$). Then follow n lines each containing $n$ non negative integers below 32,768, giving $A$’s elements in row-major order.

输出格式

Output the elements of $S$ modulo $m$ in the same way as $A$ is given.

2 2 4 
0 1 
1 1

1 2
2 3