Генератор случайных строк
Генерация строки происходит следующим образом. Строка определяется последовательностью случайных символов. Каждый символ генерируется независимо из N первых букв латинского алфавита с равной вероятностью и добавляется в конец существующей строки. Символ добавляется к строке до тех пор, пока в строке не встретится в качестве подстроки один из заданных шаблонов.
Необходимо найти математическое ожидание длины сгенерированной строки.
Входные данные
В первой строке записаны числа N и M (1 ≤ N ≤ 8, 1 ≤ M ≤ 10). N — количество используемых букв в алфавите. M — количество шаблонов. Далее записано M строк, содержащих шаблоны, состоящие из N первых букв алфавита. Длина каждого шаблона не превышает 10.
Выходные данные
Выведите математическое ожидание длины строки. Допускается абсолютная погрешность не более 10^{-3}.