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 chứa số nguyên \(n\) (\(1 \le n \le 100\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa n số nguyên của ma trận A (\(0 \le A_{i, j} < 10^9+7\)).

Định dạng đầ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 nghịch đảo \(A^{-1} \pmod{10^9+7}\), hoặc in -1 nếu ma trận không khả nghịch.

Ví dụ

Input:

2
1 2
3 4

Output:

1000000005 1
500000005 500000003

Giải thích: \(A \times A^{-1} \equiv I \pmod{10^9+7}\).

Ràng buộc & Subtasks