A. Matrix Minors
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an $$$n \times n$$$ matrix $$$A$$$. The minor $$$M_{ij}$$$ of $$$A$$$ in $$$(i,j)$$$ is the determinant of the matrix obtained from $$$A$$$ by deleting the $$$i$$$-th row and the $$$j$$$-th column. Your task is to find all minors of $$$A$$$.

Input

First line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 500$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains $$$n$$$ numbers $$$A_{i1},\dots,A_{in}$$$, the $$$i$$$-th row of $$$A$$$ ($$$0 \leq A_{ij} \lt 10^9+7$$$).

Output

Print $$$n$$$ lines, containing $$$n$$$ numbers each.

The $$$i$$$-th line should contain $$$M_{i1},\dots,M_{in}$$$, the minors of $$$A$$$.

Since the resulting numbers can be very big, print them modulo $$$10^9+7$$$.

Examples
Input
2
0 1
1 1
Output
1 1
1 0
Input
3
0 0 0
0 0 0
0 0 0
Output
0 0 0
0 0 0
0 0 0
Input
3
1 2 3
4 5 6
7 8 9
Output
1000000004 1000000001 1000000004
1000000001 999999995 1000000001
1000000004 1000000001 1000000004
Note

In the third example, the matrix $$$M$$$ is given as follows:

$$$$$$ M = -\begin{pmatrix} 3 & 6 & 3 \\ 6 & 12 & 6 \\ 3 & 6 & 3 \end{pmatrix} $$$$$$