3233 Matrix Power Series

原文

時間制限:3000ミリ秒
メモリ制限:131072KB

問題

n×nの行列Aと自然数kが与えられる。S=A+A^2+A^3+...+A^kを求めよ。

入力

入力ファイルは一つのテストケースを含みます。最初の行には三つの自然数、n(n≦30),k(k≦10^9),m(m≦10^4)が含まれています。続くn行にはそれぞれn個の32768以下の正の整数を含みます。

出力

Sの要素それぞれをｍで割った余りを、与えられたAと同じ形式で出力してください。

入力の例

2 2 4
0 1
1 1

出力の例

1 2
2 3

出典

POJ Monthly--2007.06.03, Huang, Jinsong