Cho ma trận vuông \(A\) có cỡ \(n \times n\) và số \(m\) nguyên dương, tính \(S = A^0 + A^1 + ... + A^m\).

Chú ý: \(A^0\) là ma trận vuông đơn vị cỡ \(n\).

Đầu vào

Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) \((1 \le n \le 50, 1 \le m \le 5 \times 10^9)\).

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên trong khoảng từ \(-10^4\) tới \(10^4\) là các phần tử của ma trận.

Đầu ra

\(n\) dòng, mỗi dòng chứa \(n\) số nguyên là các phần tử của ma trận \(S\) lấy mod không âm cho \(10^9 + 7\).

Subtask

\(30\%\) số test có \(n \le 10\) và \(m \le 1000\).

\(30\%\) số test khác có \(n \le 10\).

Ví dụ

Đầu vào 1:

3 3
1 1 1
1 1 1
1 1 1

Đầu ra 1:

14 13 13
13 14 13
13 13 14

Đầu vào 2:

3 2
1 0 1
0 0 0
0 0 1

Đầu ra 2:

3 0 3
0 1 0
0 0 3