Problem Description

Given an $N \times N$ matrix, find its inverse matrix. The answer should be modulo $10^9 + 7$.

Input Format

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

The next $N$ lines each contain $N$ integers, where the integer at the $i$-th row and $j$-th column represents the element $a_{ij}$ of the matrix.

Output Format

If the matrix is invertible, output $N$ lines, each containing $N$ integers, where the integer at the $i$-th row and $j$-th column represents the element $b_{ij}$ of the inverse matrix, modulo $10^9 + 7$.

Otherwise, output a single line No Solution.

Sample Input and Output

Sample Input #1

3
1 2 8
2 5 6
5 1 2

Sample Output #1

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

Sample Input #2

3
3 2 4
7 2 9
2 4 3

Sample Output #2

No Solution

Notes

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

For $100\%$ of the data, $N \le 400$ and $0 \le a_{ij} < 10^9 + 7$.

见题面 Input 部分

见题面 Output 部分