Migrated from Lutece 2994 未曾改变的夏日祭

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

又是一年夏日祭。

东云绘名（Shinonome Ena）和东云彰人（Shinonome Akito）又在一起逛夏日祭。

真好啊！真是一对关系不错的姐弟呐！

“喂，彰人，那边的摊位好像在办活动，有个奖品是薄煎饼诶！！你快去赢一份啦！”

“啊，听不见听不见 ...... 话说，你想吃的话自己去啦，别找我啦，真是的 。”

“彰人 ...... 你可想清楚咯？”

“...... 知道啦，我去。先说好，薄煎饼我也要半份。”

就这样，彰人不情愿地来到了摊位前。

这个摊位的活动是一个竞猜游戏：商家准备了 $n$ 个不同的、长度为 $l$ 的字符串，并向顾客展示这些字符串。

游戏开始前，商家从中等概率随机挑选了一个字符串，顾客则需要通过询问猜出商家选择的字符串。

顾客每一次可以询问商家字符串某个位置上是哪个字符，顾客需要在询问若干次后正确猜出商家选择的字符串。

彰人不希望因为猜错而错失薄煎饼，所以当根据已知信息暂时无法推断商家选择的字符串时，彰人会不断地询问，直到已知的信息刚好足够猜出商家选择的字符串。

难得的夏日祭，彰人也不想过多地思考策略，因此他决定每一次询问时等概率地选择一个还没有选择过的位置进行询问。

彰人想要知道，在这个竞猜游戏中自己期望需要询问多少次。

你愿意帮帮这个被姐姐使唤的可怜的弟弟吗？

Input

输入第一行包含一个整数 $n$。 接下来 $n$ 行，每行包含一个字符串，表示商家在游戏开始前展示的字符串。

Output

输出一行一个实数，表示彰人期望询问的次数。 输出请保留四位小数。只有和std输出结果完全相同才认为通过。如果认为卡精度请在clar中指出或联系出题人（lsr）。

Samples

2
ab
ac

1.5000

5
abcab
abcba
acbab
acbba
baaaa

2.5200

Constraints

$2\le n\le 50, 1\le l \le 20$，保证给定的字符串长度相等且互不相同。

Note

为了卡掉较劣的做法，本题可能有一些卡常，请注意代码实现的常数。 不过本题时限仍为出题人std的2.5倍以上。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming