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