G. Passing Ball Problem
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A football team consists of $$$n$$$ players (numbered $$$1$$$ through $$$n$$$) and a goalkeeper, and they are practicing passing.

The practice procedure is as follows:

  1. The goalkeeper kicks off first, passing the ball with equal probability to any one of the $$$n$$$ players. At this point, all players have a pass count of $$$0$$$.
  2. After receiving the ball, a player passes it according to a specific preference. If player $$$i$$$ has the ball, the probability that he passes it to player $$$j$$$ is $$$p_{i,j}$$$.
  3. Each time a player kicks the ball, their cumulative number of passes increases by $$$1$$$. If, after a pass, the number of passes for all $$$n$$$ players is exactly even, the goalkeeper will immediately step in to stop the ball, and the practice ends.

Now the goalkeeper wants to know the expected total number of passes made by the players when he stops the ball.

Input

The first line contains a positive integer $$$n$$$ ($$$1\le n \le 16$$$), denoting the number of players.

The next $$$n$$$ lines each contain $$$n$$$ integers $$$a_{i,j}$$$ ($$$0\le a_{i,j} \lt 998244353$$$). Here, after player $$$i$$$ gets the ball, the probability that they pass it to player $$$j$$$ is $$$p_{i,j} = \frac{a_{i,j}}{\sum_{k=1}^n a_{i,k}}$$$.It is guaranteed that for every $$$1\le i\le n$$$, we have $$$\left(\sum_{k=1}^n a_{i,k}\right) \not\equiv 0 \pmod{998244353}$$$.

Output

If the expectation converges, output the answer modulo $$$998244353$$$; otherwise, output infinity.

It can be proven that if the expectation converges, then it can always be written as a rational number $$$\frac{p}{q}$$$, where $$$p,q$$$ are integers, $$$p\ge 0$$$, and $$$q\ge 1$$$. You should output the value of $$$p\cdot q^{-1}\bmod 998244353$$$, where $$$q^{-1}$$$ denotes the modular inverse of $$$q$$$ modulo $$$998244353$$$, which satisfies $$$q \cdot q^{-1} \equiv 1 \pmod {998244353}$$$.

Examples
Input
5
1 0 0 0 0
2 1 0 0 0
3 0 1 0 0
4 0 0 1 0
5 0 0 0 1
Output
infinity
Input
5
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
Output
10
Input
6
5 6 499122175 10 10 998244352
7 998244351 7 4 499122176 3
4 10 2 9 8 9
6 6 6 3 10 10
998244351 3 1 499122175 10 9
3 7 6 499122176 499122176 3
Output
53368493
Input
1
8
Output
2