Limits 5s, 512 MB

This problem is very easy. There's a graph of $N$ nodes. Each edge $u-v$ ($u >= v ; u = v$ is possible, i.e. a loop) has some probability $P(u, v)$ of existing. Given these probabilities, you have to find out the expected number of connected components of such a graph created according to the probabilities.

Input

The first line contains an integer $N$. After that, there are $N$ lines of input. The ith line has i numbers on it. jth number of ith line represents the probability $P(i, j)$ in percentage. All input numbers are integers.

$1 \leq N \leq 17$
$0 \leq P(i, j) \leq 100$

Output

The expected number of connected components can be represented as $P/Q$, where $P$ and $Q$ are natural numbers. Output $P \times Q^{-1}$ mod $998244353$.

Samples

InputOutput
2
50
50 50
499122178

When the 1-2 edge exists, there is 1 connected component. Otherwise there are 2 components. So the answer is (1+2)1/2 = 3/2 which is 32-1 = 499122178 in mod 998244353.

InputOutput
3
50
50 100
50 100 0
748683266

Submit

Login to submit.

Statistics

87% Solution Ratio
NirjhorEarliest, Dec '19
Kuddus.6068Fastest, 0.2s
clist.byLightest, 1.2 MB
omar24Shortest, 1041B
Toph uses cookies. By continuing you agree to our Cookie Policy.