问题描述

我们有一个有向图，其中 $N$ 个顶点从 $1$ 到 $N$ 编号。长度为 $N$ 的 $N$ 个字符串 $S_1,S_2,\ldots,S_N$ 表示图中的边。具体来说，如果从顶点 $i$ 到顶点 $j$ 有一条边，则 $S_{i,j}$ 为 1，否则为 0。图中没有自环和多重边。

直到图变为空，AtCobear将重复以下操作：

• 均匀随机选择一个（未擦除）顶点（与之前的选择独立）。然后，擦除该顶点以及通过一些边可达的所有顶点。擦除一个顶点也将擦除与之相邻的边。

找出操作次数的期望值。

约束条件

• $1 \leq N \leq 100$
• $S_i$ 是一个由 0 和 1 组成的长度为 $N$ 的字符串。
• $S_{i,i}=$0

输入格式

输入以以下格式从标准输入中给出：

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

输出格式

输出操作次数的期望值。当输出的绝对误差或相对误差不超过 $10^{-9}$ 时，你的输出将被认为是正确的。

示例输入1

3
010
001
010

示例输出1

1.66666666666666666667

三种情况以相等的概率发生：

• 在第一次操作中选择顶点 $1$，擦除顶点 $1$、$2$ 和 $3$。现在，图为空，我们完成了。

• 在第一次操作中选择顶点 $2$，擦除顶点 $2$ 和 $3$。然后，在第二次操作中选择顶点 $1$，擦除顶点 $1$。现在，图为空，我们完成了。

• 在第一次操作中选择顶点 $3$，擦除顶点 $2$ 和 $3$。然后，在第二次操作中选择顶点 $1$，擦除顶点 $1$。现在，图为空，我们完成了。

因此，操作次数的期望值为 $(1+2+2)/3=5/3$。

示例输入2

3
000
000
000

示例输出2

3.00000000000000000000

总共需要三次操作。

示例输入3

3
011
101
110

示例输出3

1.00000000000000000000

总共需要一次操作。