Background

Once, abruce went to the computer lab quite early, and then... he waited outside for 35 minutes... So he thought of this question:
The door of the computer lab is locked. There are $n$ students who all need to get in, and to enter they must have an access card. However, some students may go together. For a group that goes together, as long as at least one person brings an access card, they will not be awkwardly locked outside. Now the teacher is finally going to hand out access cards, but how many cards should be given out?

Problem 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