Phép cộng hai ma trận có cùng kích thước \(m \times n\), ma trận tổng \(C=A+B\) có kích thước \(m \times n\), phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận bên phải. Nếu ma trận \(A\) có kích thước \(m \times n\) và ma trận \(B\) có kích thước \(n \times p\), thì ma trận \(C=A \times B\) có kích thước \(m \times p\), phần tử ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

Phép nhân ma trận có các tính chất sau:

• Tính chất kết hợp: \((A \times B) \times C=A \times (B \times C);\)
• Tính chất phân phối: \((A+B) \times C=A \times C+B \times C; C \times (A+B)=C \times A+C \times B\)

Cần chú ý rằng phép nhân ma trận không giao hoán.

Ví dụ, cho \(A=\begin{pmatrix}0&1\\1&1\end{pmatrix}\), ta có \(A^2=\begin{pmatrix}1&1\\1&2\end{pmatrix}\), \(A^3=\begin{pmatrix}1&2\\2&3\end{pmatrix}, ...\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n \times n\) và số nguyên dương \(k\), hãy tính \(B=A+A^2+...+A^{k}\).

Input

• Dòng đầu chứa hai số nguyên \(n, k\) (\(n \le 20\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên.

Output

• Gồm \(n\) dòng, mỗi dòng \(n\) số mô tả ma trận \(B\). Vì giá trị mỗi phần tử của ma trận \(B\) có thể rất lớn, do đó chỉ cần đưa ra chữ số cuối cùng của từng phần tử của ma trận \(B\).

Example

2 3
0 1
1 1

2 4
4 6

Scoring

• Subtask \(1\): \(k \le 10^2\).
• Subtask \(2\): \(k \le 10^9\).

Tài liệu gốc: matrix.pdf