[SDOI2014]重建

题目描述

T 国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。 在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。 幸运的是,此前 T 国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有 $N-1$ 条,且能联通所有城市的概率。

输入输出格式

输入格式


输入的第一行包含整数 $N$。 接下来 $N$ 行,每行 $N$ 个实数,第 $i+1$ 行,列的数 $G_{i,j}$ 表示城市 $i$ 与 $j$ 之间仍有道路联通的概率。 输入保证 $G_{i,j}=G_{j,i}$,且 $G_{i,i}=0$。$G_{i, j}$ 至多包含两位小数。

输出格式


输出一个任意位数的实数表示答案。 你的答案与标准答案相对误差不超过 $10^{-4}$ 即视为正确。

输入输出样例

输入样例 #1

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0

输出样例 #1

0.375

说明

$1<N\leq 50$。 数据保证答案非零时,答案不小于 $10^{-4}$。