Генерация строки происходит следующим образом. Строка определяется последовательностью случайных символов. Каждый символ генерируется независимо из \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\}}.