408813: GYM103328 J Hot Potato

Jason lives in Gotham. This summer, he plays a game called Hot Potato with people there.

The game consisted of $$$n$$$ players numbered from $$$1$$$ to $$$n$$$ and a hot potato. Initially, player $$$1$$$ holds the hot potato. When a player holds the hot potato, he/she must pass it to another player, otherwise, the holder is the loser, and the game ends. Suppose A is the player holding the hot potato and B is any other player. A can only pass the hot potato to B if A knows B and B hasn't touched the hot potato before. Note that A knows B does not imply B knows A.

People of Gotham love chaos, so if there are multiple players A can choose to pass the hot potato, A chooses one uniformly at random. In other words, if there are $$$k$$$ candidates, each of them has the probability of $$$\frac{1}{k}$$$ to be chosen by A.

Jason knows the relationships between players and wants to know the probability of losing the game for each player. Please help him!

The first line of the input contains a positive integer $$$n$$$. Each of the next $$$n$$$ lines contains $$$n$$$ integers separated by a single space. Let $$$G_{i,j}$$$ be the $$$j$$$-th number of the $$$i$$$-th line. If $$$G_{i,j} = 0$$$, then player $$$i$$$ doesn't know player $$$j$$$. If $$$G_{i,j} = 1$$$, then player $$$i$$$ knows player $$$j$$$.

• $$$1 \leq n \leq 20$$$
• $$$G_{i,j} \in \{0, 1\}$$$, for all $$$1 \leq i, j \leq n$$$
• $$$G_{i,i} = 0$$$, for all $$$1 \leq i \leq n$$$

Let $$$p_i$$$ be the probability of losing for player $$$i$$$. It can be proved that $$$p_i$$$ is a rational number. Let $$$\frac{a_i}{b_i}$$$ be $$$p_i$$$'s simplest form. (i.e. $$$\frac{a_i}{b_i}=p_i$$$ and $$$\gcd(a_i, b_i) = 1$$$). Let $$$M=1000000007$$$. Let $$$v_i \equiv a_i {b_i}^{-1} \pmod{M}$$$.

Output a single line with $$$n$$$ numbers separated by a single space. The $$$i$$$-th of them should be $$$v_i$$$. ($$$0 \leq v_i < M$$$)

3
0 1 1
1 0 1
1 1 0

0 500000004 500000004

2
0 1
0 0

0 1

4
0 1 0 1
1 0 1 1
1 1 0 0
1 0 0 0

0 0 250000002 750000006