22176번 - Вирусы 다국어

В некоторой антивирусной компании занимаются исследованием вирусов. Им известно о существовании m типов вирусов. Каждый вирус задается строкой из строчных букв латинского алфавита. Вирусам разного типа соответствуют разные строки.

Недавно начались исследования ранее не изучавшихся объектов — полностью зараженных строк. Строка s называется полностью зараженной, если для любого ее символа существует подстрока s, содержащая этот символ и являющаяся вирусом.

Ваша задача — по заданным вирусам найти количество полностью зараженных строк длины n. Так как это число может быть очень большим, выведите его по модулю 10⁹+7.

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 400; 1 ≤ m ≤ 20).

Далее в m строках задано описание вирусов. В каждой из этих строк задана последовательность строчных букв латинского алфавита.

Длина каждого вируса положительна и не превосходит 20 символов.

Выведите единственное целое число — остаток от деления числа полностью зараженных строк на 10⁹+7.