http://poj.org/problem?id=3233
//* @author:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Main{
static int n, k, m;
static int[][] matrix;
static int[][] result;
/**
* ������a��Ԫ�ظ��Ƶ�����һ������
*
* @param a
* @return
*/
static int[][] copy(int[][] a) {
int[][] re = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
re[i][j] = a[i][j];
return re;
}
/**
* ���}������Ͳ�ȡ��%m
*
* @param a
* @param b
*/
static void add(int[][] a, int[][] b) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
a[i][j] += b[i][j];
a[i][j] %= m;
}
}
/**
* ����}����Ļ�ȡ��%m
*
* @param a
* @param b
* @return
*/
static int[][] mul(int[][] a, int[][] b) {
int[][] re = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
long t = 0;
for (int k = 0; k < n; k++) {
t += 1L * a[i][k] * b[k][j];
}
re[i][j] = (int) (t % m);
}
return re;
}
/**
* ����matrix��p����%m
*
* @param p
* @return
*/
static int[][] powm(int p) {
if (p == 1)
return matrix;
int[][] re = powm(p / 2);
re = mul(re, re);
if (p % 2 == 1)
re = mul(re, matrix);
return re;
}
/**
* ����A + A2 + A3 + �� + Ak�ĺ�%m
*
* @param lk
* @return
*/
static int[][] calc(int lk) {
if (lk == 1)
return copy(matrix);
int mid = lk / 2;
if (lk % 2 == 1)
mid++;
//����A + A2 + A3 + �� +Ai
int[][] re1 = calc(lk / 2);
//����Ai
int[][] fac = powm(mid);
int[][] re = mul(fac, re1);
add(re, re1);
if (lk % 2 == 1)
add(re, fac);
return re;
}
public static void main(String[] args) throws Exception {
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
// ��ȡn,k,m
String s = cin.readLine();
String[] sa = s.split(" ");
n = Integer.parseInt(sa[0]);
k = Integer.parseInt(sa[1]);
m = Integer.parseInt(sa[2]);
matrix = new int[n][n];
result = new int[n][n];
for (int i = 0; i < n; i++) {
s = cin.readLine().trim();
sa = s.split(" ");
for (int j = 0; j < n; j++)
matrix[i][j] = Integer.parseInt(sa[j]);
}
int[][] re = calc(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
out.print(re[i][j] + " ");
}
out.println();
}
out.flush();
out.close();
}
}