题目描述

有一个单词数据库，计算机会从其中 等概率随机选择 一个单词。随后，两名玩家轮流猜测这个隐藏单词，第一名玩家先手。

游戏过程中，已经确定的字符会被显示出来，其他位置显示为短横线。当前玩家在自己的回合中可以选择以下两种操作之一：

1. 猜一个字符。

   • 如果这个字符出现在隐藏单词中，则显示这个字符的所有出现位置，并且当前玩家继续行动；
   • 如果这个字符没有出现在隐藏单词中，则回合交给另一名玩家。

2. 直接猜整个单词。

   • 如果猜对，游戏立即结束，当前玩家获胜；
   • 如果猜错，回合交给另一名玩家。

两名玩家都知道完整的单词数据库，并且都会采用使自己最终获胜概率最大的策略。

请计算在双方均采用最优策略时，先手玩家获胜的概率。

输入格式

第一行输入一个整数 $n$，表示单词数量。

接下来 $n$ 行，每行输入一个只包含小写英文字母的字符串，表示一个候选单词。

所有单词长度相同，并且两两不同。

输出格式

输出一个实数，表示双方均采用最优策略时先手玩家获胜的概率。

答案的绝对误差或相对误差不超过 $10^{-9}$ 即可。

样例 1

输入

5
top
web
cam
buy
now

输出

0.6

样例 2

输入

4
wwtkmcoj
lgsyduoi
oiqisear
hntxjrkf

输出

0.75

样例 3

输入

1
a

输出

1.0

样例 4

输入

5
ppk
bez
ltm
nev
roo

输出

0.6

样例 5

输入

9
advanced
absolute
anything
accepted
reflects
cleverly
coaching
winnings
overflow

输出

0.6666666666666666

样例解释

样例 1 中，先手首先猜字符 w 是一种最优策略。

如果隐藏单词包含 w，会显示 w-- 或 --w，此时先手能够确定单词并继续猜中它；如果 w 不存在，则轮到后手。最终先手能保证在隐藏单词为 web、cam 或 now 时获胜，因此获胜概率为 $3/5=0.6$。

数据范围

• $1\le n\le 10$；
• 每个单词长度在 $1$ 到 $50$ 之间；
• 所有单词长度相同；
• 所有字符均为小写英文字母；
• 所有单词两两不同；
• 每个单词被计算机选中的概率均为 $1/n$。