Country T has $N$ cities connected by several bidirectional roads. There is at most one road between any pair of cities.
After a flood, some roads were damaged and became impassable. Although people have started to investigate the damage, almost no information has been returned yet.
Fortunately, the government of Country T had previously surveyed the strength of each road, and they now hope to use this information to estimate the disaster situation. Specifically, given the probability that each road remains passable after the flood, calculate the probability that exactly $N-1$ roads remain passable and that all cities are connected.
Input
The first line contains an integer $N$.
The next $N$ lines each contain $N$ real numbers. The number in the $i$-th row and $j$-th column, $G[i][j]$, represents the probability that a road still exists between city $i$ and city $j$.
The input guarantees $G[i][j] = G[j][i]$ and $G[i][i] = 0$. $G[i][j]$ contains at most two decimal places.
Output
Output the answer as a real number with any number of decimal places.
Your answer is considered correct if the relative error compared to the standard answer does not exceed $10^{-4}$.
Constraints
| Test Case | $N$ | Other Constraints |
|---|---|---|
| 1 | $1 \le N \le 10$ | $G[i][j]$ are integers |
| 2, 3 | $1 \le N \le 10$ | Number of edges with non-zero probability $\le 20$ |
| 4, 5 | $1 \le N \le 12$ | |
| 6, 7 | $1 \le N \le 16$ | |
| 8, 9 | $1 \le N \le 50$ | No edges with probability $1$ exist |
| 10 | $1 \le N \le 50$ |
It is guaranteed that if the answer is non-zero, it is not less than $10^{-4}$.
Examples
Input 1
3 0 0.5 0.5 0.5 0 0.5 0.5 0.5 0
Output 1
0.375
Input 2
5 0.00 0.95 0.96 0.95 0.00 0.95 0.00 0.95 0.95 0.96 0.96 0.95 0.00 0.85 0.02 0.95 0.95 0.85 0.00 0.85 0.00 0.96 0.02 0.85 0.00
Output 2
0.0006095519875