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).
Each column of sums to exactly .
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 space-separated numbers, the entries of the unique vector .
2 900000007 500000004 100000001 500000004
Explanation for Sample
We are given the transition matrix of
and find that its steady-state vector is .