Критичне неправильне прочитання#3448

Критичне неправильне прочитання

1 секунда
128 мегабайтів

Вам задано рядків s_1, s_2, \ldots, s_k, що складаються з малих латинських літер.

Знайдіть кількість рядків довжини , що складаються з малих латинських літер, які не містять жодного з рядків s_1, s_2, \ldots, s_k як підрядок (неперервну послідовність символів). Оскільки ця кількість може бути великою, виведіть її за модулем .

Вхідні дані

Перший рядок містить два цілих числа та k~(1 \le n \le 10^9, 1 \le k \le 10) — довжину рядків, які потрібно порахувати, та кількість заборонених рядків.

Кожен з наступних рядків містить один рядок s_i. Кожен рядок складається з малих латинських літер і має довжину від до включно.

Вихідні дані

Виведіть одне ціле число — кількість рядків довжини , які не містять жодного з рядків s_i як підрядок, за модулем .

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading