Генератор випадкових рядків#3698
Генерація рядка відбувається наступним чином. Рядок формується як послідовність випадкових символів. Кожен символ генерується незалежно з перших літер латинського алфавіту з однаковою ймовірністю і додається в кінець існуючого рядка. Процес триває, поки в рядку не з'явиться один із заданих шаблонів як підрядок.
Ваше завдання — знайти математичне сподівання довжини згенерованого рядка.
У першому рядку подано числа і (1 \le N \le 8, 1 \le M \le 10). — кількість літер, що використовуються в алфавіті. — кількість шаблонів. Далі йдуть рядків, що містять шаблони, які складаються з перших літер алфавіту. Довжина кожного шаблону не перевищує .
Виведіть математичне сподівання довжини рядка. Допустима абсолютна похибка не більше 10^{-3}.
Приклад 1