C. Игра со строками
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в игру со своим другом. Ниже приведено описание этой игры.

Ваш друг придумывает n различных строк одинаковой длины m и сообщает вам все строки. Далее он выбирает случайным образом одну из них. Он выбирает строки равновероятно, то есть вероятность выбора каждой из n строк равна . Вы хотите угадать, какую из строк выбрал ваш друг.

Для того, чтобы угадать строку, загаданную другом, вам разрешается задавать другу вопросы. Каждый вопрос имеет следующую форму: «Какой символ стоит на позиции pos в загаданной тобой строке?». Строка считается угаданной, когда ответы на заданные вопросы однозначно определяют загаданную строку. После того, как строка становится угаданной, вы прекращаете задавать вопросы.

У вас нет определённой стратегии, поэтому очередным вопросом вы каждый раз равновероятно выбираете одну из еще не названных позиций. Ваша задача — определить математическое ожидание количества вопросов, необходимых для того, чтобы угадать выбранную вашим другом строку.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 50) — количество строк, придуманных вашим другом.

В следующих n строках заданы строки, придуманные вашим другом. Гарантируется, что все строки различны и состоят только из строчных и прописных букв латинского алфавита. Кроме того, длины всех строк одинаковы и лежат в промежутке от 1 до 20 включительно.

Выходные данные

Выведите единственное число — искомое математическое ожидание. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10 - 9.

Примеры
Входные данные
2
aab
aac
Выходные данные
2.000000000000000
Входные данные
3
aaA
aBa
Caa
Выходные данные
1.666666666666667
Входные данные
3
aca
vac
wqq
Выходные данные
1.000000000000000
Примечание

В первом примере придуманные строки различаются только символом в третьей позиции. Поэтому возможны следующие ситуации:

  • вы угадаете загаданную строку за один вопрос. Вероятность этого события ;
  • вы угадаете загаданную строку за два вопроса. Вероятность этого события равна · = (поскольку в таком случае первым вопросом нужно спросить про позицию отличную от трех);
  • вы угадаете загаданную строку за три вопроса. Вероятность этого события равна · · = ;

Таким образом искомое математическое ожидание равно

Во втором примере нам максимум может потребоваться два вопроса, поскольку любая пара вопросов определяет строку. Поэтому искомое математическое ожидание равно .

В третьем примере, независимо от того, про какую позицию мы спросим первым вопросом, мы сразу угадаем загаданную строку.