행렬 제곱

크기가 $N \times N$인 행렬 $A$와 지수 $B$가 주어진다. $A^B$를 구하는 프로그램을 작성한다.

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

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

둘째 줄부터 $N$개의 줄에 행렬 $A$의 각 행이 주어진다. 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

$N$개의 줄에 걸쳐 $A^B$를 출력한다. $i$번째 줄에는 $i$번째 행의 원소 $N$개를 공백으로 구분해 출력하고, 각 원소는 1,000으로 나눈 나머지를 출력한다.