Вам задано рядків 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
Приклад 2
Приклад 3