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

\(c_{i,j} = a_{i,j}+b_{i,j}\)

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\) x \(n\) và ma trận \(B\) có kích thước \(n \times p\), thì ma trận tích \(C=A\)x\(B\) có kích thước\(m\) x \(p\) , phần tử đứng ở hàng thứ \(i\) , cột thứ \(j\) xác định bởi:

\(c_{i,j} = a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+...+a_{i,n}b_{n,j}\)

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

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

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

Ví dụ:

\(A\) = \(\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}\) ,\(A^2\) = \(\begin{pmatrix} 1 & 1\\ 1 & 2 \end{pmatrix}\) ,\(A^3\) = \(\begin{pmatrix} 1 & 2\\ 2 & 3 \end{pmatrix}\) ,\(A+A^2+A^3\) = \(\begin{pmatrix} 2 & 4\\ 4 & 6 \end{pmatrix}\) .

Yêu cầu

Cho ma trận \(A\) kích thước \(n×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\leq 20)\).
• \(n\) dòng tiếp theo, mỗi dòng chứa số nguyên.

Output

• Gồm \(n\) dòng, mỗi dòng 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

Subtask 1: \(k \leq 10^2\).

Subtask 2: \(k \leq 10^9\)