Problems
Генератор случайных строк
Генератор случайных строк
Генерация строки происходит следующим образом. Строка определяется последовательностью случайных символов. Каждый символ генерируется независимо из \textbf{N} первых букв латинского алфавита с равной вероятностью и добавляется в конец существующей строки. Символ добавляется к строке до тех пор, пока в строке не встретится в качестве подстроки один из заданных шаблонов.
Необходимо найти математическое ожидание длины сгенерированной строки.
\InputFile
В первой строке записаны числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N} ≤ \textbf{8}, \textbf{1} ≤ \textbf{M} ≤ \textbf{10}). \textbf{N} --- количество используемых букв в алфавите. \textbf{M} --- количество шаблонов. Далее записано \textbf{M} строк, содержащих шаблоны, состоящие из \textbf{N} первых букв алфавита. Длина каждого шаблона не превышает \textbf{10}.
\OutputFile
Выведите математическое ожидание длины строки. Допускается абсолютная погрешность не более \textbf{10^\{-3\}}.
Input example #1
2 1 ABA
Output example #1
10.00000