P4783 [Template] Matrix Inversion

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

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.

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`.

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