Description

We simplify the problem in the background. You are given $n$ points, and for any two points $i,j$, there is an undirected edge between them with probability $p_{i,j}$. Find the expected number of connected components in the graph.

Input Format

The first line contains an integer $n$.
Lines $2$ to $n+1$ each contain $n$ real numbers, representing $p_{i,j}$. The testdata guarantees that for any $1\le i \le n$, $p_{i,i}=0$; for any $1\le i,j \le n$, $p_{i,j}=p_{j,i}$; $0\le p_{i,j}\le1$. The input real numbers have at most $3$ digits after the decimal point.

Output Format

Output one real number in a single line, representing the expected number of connected components. Your answer is considered correct if the absolute error from the standard answer does not exceed $10^{-4}$.

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0

1.625000

4
0 0.129 0.58 0.37
0.129 0 0.22 0.134
0.58 0.22 0 0.6
0.37 0.134 0.6 0

2.143266

Hint

Sample Explanation 1: The following eight cases each occur with probability $\dfrac{1}{8}$.

The numbers of connected components are $3,2,2,2,1,1,1,1$.
So the expectation is $\dfrac{1}{8}\times3+\dfrac{3}{8}\times2+\dfrac{4}{8}\times1=\dfrac{13}{8}=1.625$

Constraints:

Translated by ChatGPT 5