eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Генератор случайных строк

Генератор случайных строк

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

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

Необходимо найти математическое ожидание длины сгенерированной строки.

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

В первой строке записаны числа N и M (1N8, 1M10). N — количество используемых букв в алфавите. M — количество шаблонов. Далее записано M строк, содержащих шаблоны, состоящие из N первых букв алфавита. Длина каждого шаблона не превышает 10.

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

Выведите математическое ожидание длины строки. Допускается абсолютная погрешность не более 10^{-3}.

Пример

Входные данные #1
2 1
ABA
Выходные данные #1
10.00000
Источник III Международная Летняя школа программирования 2012 г. Севастополь