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\mathrm{\%}$ số test có $n\le 10$ và $m\le 1000$.

$30\mathrm{\%}$ 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