크기가 N*N인 행렬 A가 주어진다. 이때, A의 1제곱부터 A의 B제곱까지 더한 행렬을 구하는 프로그램을 작성하시오. 즉, S = A¹ + A² + ... + A^B를 구해야 한다.</p>

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

입력 형식

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)</p>

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

출력 형식

첫째 줄부터 N개의 줄에 걸쳐 행렬 S를 출력한다.

예제 입력 1

2 5
1 2
3 4

예제 출력 1

313 914
871 184

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

499 614 729
132 391 650
765 168 571

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

23 0 0 0 23
23 0 0 0 23
23 0 0 0 23
23 0 0 0 23
23 0 0 0 23