시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 18 10 10 55.556%

문제

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

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

입력

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

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

출력

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

예제 입력

2 5
1 2
3 4

예제 출력

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

힌트

출처