// BOJ 10830번 : 행렬 제곱
#include <iostream>
using namespace std;
void matrix(int a[5][5], int b[5][5]);
long long n, b;
int arr[5][5];
int result[5][5];
int tmp[5][5];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> b;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> arr[i][j];
}
result[i][i] = 1; // result 배열 초기화
}
while(b){ // b가 0이 아닐 떄까지
if(b % 2 == 1){ // 홀수일 때
matrix(result, arr);
}
matrix(arr, arr); // 짝수일 때
b /= 2; // 2로 나누기
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << result[i][j] << " "; // 배열 출력
}
cout << "\n";
}
}
void matrix(int a[5][5], int b[5][5]){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
tmp[i][j] = 0; // tmp 초기화
for(int k = 0; k < n; k++){ // a와 b 곱한 값 tmp에 넣기
tmp[i][j] += a[i][k] * b[k][j];
}
tmp[i][j] %= 1000; // 값을 1000으로 나눈 나머지 저장
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
a[i][j] = tmp[i][j]; // tmp의 값을 a배열(result)에 다시 저장
}
}
}
A^n을 A x A x ... A^n 이렇게 곱하면 시간초과
빠른 거듭제곱 알고리즘