Генератор випадкових рядків

Генерація рядка відбувається наступним чином. Рядок формується як послідовність випадкових символів. Кожен символ генерується незалежно з N перших літер латинського алфавіту з однаковою ймовірністю і додається в кінець існуючого рядка. Процес триває, поки в рядку не з'явиться один із заданих шаблонів як підрядок.

Ваше завдання — знайти математичне сподівання довжини згенерованого рядка.

Вхідні дані

У першому рядку подано числа N і M (1 ≤ N ≤ 8, 1 ≤ M ≤ 10). N — кількість літер, що використовуються в алфавіті. M — кількість шаблонів. Далі йдуть M рядків, що містять шаблони, які складаються з N перших літер алфавіту. Довжина кожного шаблону не перевищує 10.

Вихідні дані

Виведіть математичне сподівання довжини рядка. Допустима абсолютна похибка не більше 10^{-3}.

Приклади