eolymp
bolt
Try our new interface for solving problems
Problems

Вирусы

Вирусы

Time limit 2 seconds
Memory limit 256 MiB

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

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

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

Input data

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

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

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

Output data

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

Examples

Input example #1
5 2
aba
babc
Output example #1
2
Source Russian-Code-Cup-2011 Отборочный раунд