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