행렬 곱셈 최적화

N×N 행렬 M의 K제곱을 구하여라. K가 최대 10^18이므로 행렬 빠른 거듭제곱을 사용해야 한다. 결과의 각 원소는 10^9+7로 나눈 나머지를 출력한다.

입력

첫째 줄에 N, K, 이후 N개의 줄에 행렬의 각 행이 주어진다.

• 1 ≤ N ≤ 5
• 1 ≤ K ≤ 10^18
• 0 ≤ 각 원소 ≤ 10^9

출력

M^K mod (10^9+7)의 각 행을 공백으로 구분하여 출력한다.

예제 입력 1

2 3
1 2
3 4

예제 출력 1

37 54
81 118