Cho ma trận vuông \(A\) kích thước \(n \times n\). Tìm ma trận nghịch đảo \(A^{-1}\) modulo \(10^9+7\). Nếu ma trận không khả nghịch, in \(-1\).

Định dạng đầu vào

• Dòng đầu: \(n\) (\(1 \le n \le 100\)).
• \(n\) dòng tiếp: mỗi dòng \(n\) số nguyên.

Định dạng đầu ra

• \(n\) dòng, mỗi dòng \(n\) số là ma trận nghịch đảo, hoặc \(-1\) nếu không khả nghịch.

Ví dụ

Input:

2
1 2
3 4

Output: ``` ...

Giải thích: \(A \times A^{-1} = I\).

Ràng buộc

• 100% số điểm: \(n \le 100\).