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

For this problem, input and output will be done modulo . This means that if is some fraction where , then you're given the integer modulo (and the same is true for output).

#### Constraints

Each column of sums to exactly .

#### Input Specification

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

The next lines contain space-separated numbers, representing the matrix (as defined above). The -th integer on the -th row contains .

#### Output Specification

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

#### Sample Input

```
2
900000007 500000004
100000001 500000004
```

#### Sample Output

`625000005 375000003`

#### Explanation for Sample

We are given the transition matrix of

and find that its steady-state vector is .

## Comments