Problem Description

Find the inverse matrix of an $N\times N$ matrix. Output the answer modulo ${10}^9+7$.

Input Format

The first line contains an integer $N$, which represents the size of the matrix.

The next $N$ lines each contain $N$ integers. The number in row $i$ and column $j$ represents the element $a_{i j}$ of the matrix.

Output Format

If the matrix is invertible, output $N$ lines, each containing $N$ integers. The number in row $i$ and column $j$ represents the element $b_{i j}$ of the inverse matrix, taken modulo ${10}^9+7$.

Otherwise, output only one line: No Solution.

3
1 2 8
2 5 6
5 1 2

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

3
3 2 4
7 2 9
2 4 3

No Solution

Hint

For $30\%$ of the testdata, $N\le 100$.

For $100\%$ of the testdata, $N\le 400$, and all $0 \le a_{i j} < {10}^9 + 7$.

Translated by ChatGPT 5