Description

Country T has $N$ cities, connected by several bidirectional roads. Between any pair of cities, there is at most one road.

After a flood, some roads were damaged and are no longer passable. Although an investigation into the damage has begun, almost no information has come back so far.

Fortunately, the government of Country T had previously investigated the strength of each road, and now they hope to estimate the damage using only this information. Specifically, given for each road the probability that it remains passable after the flood, compute the probability that exactly $N-1$ roads remain passable and they connect all cities.

Input Format

The first line contains the integer $N$.

Then follow $N$ lines, each containing $N$ real numbers. In the $(i+1)$-th line, the number in column $j$, denoted $G_{i,j}$, represents the probability that cities $i$ and $j$ are still connected by a road after the flood.

It is guaranteed that $G_{i,j}=G_{j,i}$ and $G_{i,i}=0$. Each $G_{i,j}$ contains at most two decimal places.

Output Format

Output a real number representing the answer.

Your answer will be accepted if its relative error does not exceed $10^{-4}$.

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0

0.375

Hint

$1 < N \leq 50$.

It is guaranteed that if the answer is non-zero, then it is at least $10^{-4}$.

Translated by ChatGPT 5