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
Copy
2
900000007 500000004
100000001 500000004
Sample Output
Copy
625000005 375000003
Explanation for Sample
We are given the transition matrix of

and find that its steady-state vector is
.
Comments