You are given the $N\times N$ transition matrix for a regular Markov chain, and you need to find its steady state vector. Formally, given an $N\times N$ matrix $P$, you need to find the unique vector $v$ such that

• $Pv=v$
• $0\le v_1,\dots ,v_N\le 1$
• $\sum _{i=1}^N{v}_i=1$

For this problem, input and output will be done modulo ${10}^9+7$. This means that if $P_{ij}$ is some fraction $A/B$ where $0<A\le B$, then you're given the integer $A\cdot B^{-1}$ modulo ${10}^9+7$ (and the same is true for output).

Constraints

$1\le N\le 500$

$0<P_{ij}\le 1$

Each column of $P$ sums to exactly $1$.

Input Specification

The first line contains an integer, $N$, the number of possible events to consider.

The next $N$ lines contain $N$ space-separated numbers, representing the matrix $P$ (as defined above). The $j$-th integer on the $i$-th row contains $P_{ij}$.

Output Specification

Output $N$ space-separated numbers, the entries of the unique vector $v$.

Sample Input

2
900000007 500000004
100000001 500000004

Sample Output

625000005 375000003

Explanation for Sample

We are given the transition matrix of

$${\displaystyle P=\left[\begin{array}{cc}7/10& 1/2\\ 3/10& 1/2\end{array}\right]}$$

and find that its steady-state vector is $v=⟨5/8,3/8⟩$.