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