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=\begin{bmatrix}7/10 & 1/2 \\ 3/10 & 1/2\end{bmatrix}$$

and find that its steady-state vector is ~v = \langle 5/8, 3/8 \rangle~.