행렬 제곱의 합

크기가 $N \times N$인 행렬 $A$가 주어진다. $A$의 1제곱부터 $B$제곱까지 모두 더한 행렬

$S = A^1 + A^2 + \cdots + A^B$

를 구하는 프로그램을 작성하시오.

원소가 매우 커질 수 있으므로, $S$의 각 원소를 1,000으로 나눈 나머지를 출력한다.

첫째 줄에 행렬의 크기 $N$과 지수의 상한 $B$가 공백으로 구분되어 주어진다. ($2 \le N \le 5$, $1 \le B \le 100{,}000{,}000{,}000$)

둘째 줄부터 $N$개의 줄에 걸쳐 행렬 $A$의 원소가 한 줄에 $N$개씩 공백으로 구분되어 주어진다. 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

$N$개의 줄에 걸쳐 행렬 $S$를 출력한다. $i$번째 줄에는 $S$의 $i$번째 행에 있는 원소 $N$개를 1,000으로 나눈 나머지를 공백으로 구분해 출력한다.