덴마크어

Boschua는 LTH에서 공부하기 위해 Lund로 이사한다. 당신은 Lund가 Skåne에 있다는 것을 알게 되었고, 이제 Boschua의 말투가 덴마크어처럼 들리기 시작할까 봐 걱정한다.

이를 막기 위해, 당신은 Boschua에게 전혀 덴마크어처럼 들리지 않는 단어가 얼마나 많은지 보여 주고 싶다. 당신에 따르면, 어떤 단어가 덴마크어 사전에 있는 단어를 적어도 하나 포함하면 그 단어는 덴마크어처럼 들린다. 안타깝게도 공식 덴마크어 사전을 이용할 수 없지만, 지하실에서 발견한 오래된 사전으로 만족해야 한다.

예를 들어, 사전에 knallert라는 단어만 들어 있다고 하자. 그러면 hus**knallert**rumma라는 단어는 knallert를 포함하므로 덴마크어처럼 들린다고 간주한다. 반면, **knaller**un**t**라는 단어는 knallert를 포함하지 않으므로 덴마크어처럼 들리지 않는다고 간주한다.

husknallertrumma라는 단어는 덴마크어처럼 들린다.

knallerunt라는 단어는 덴마크어처럼 들리지 않는다.

당신은 덴마크어처럼 들리지 않는 단어가 너무 많아 모두 나열할 수 없다는 것을 금세 깨닫는다. 따라서 덴마크어처럼 들리지 않는 단어의 수를 세어 Boschua에게 알려 주는 것으로 충분하다고 결정한다. 덴마크어처럼 들리지 않는 단어가 워낙 많아서 이마저도 어렵다는 것이 드러난다.

마침내 소문자 영어 알파벳 a-z로만 이루어지고, 글자 수가 정확히 $N$개이며, 덴마크어처럼 들리지 않는 단어의 수를 세기로 한다. 어떤 단어가 사전에 있는 단어를 부분 문자열로 적어도 하나 포함하면 그 단어는 덴마크어처럼 들린다.

채점

당신의 풀이는 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 평가된다. 각 테스트 그룹에는 테스트 케이스들의 집합이 포함된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$10$| $M = 0$

$2$ |$13$| $N \leq 3, M \leq 10$

$3$ |$23$| $M = 1$

$4$ |$32$| $N, M \leq 50$

$5$ |$22$| 추가 제약 조건이 없다.

입력의 첫째 줄에는 고려하는 단어의 길이와 사전에 있는 단어의 수를 나타내는 정수 $N$ ($1 \leq N \leq 100$)와 $M$ ($0 \leq M \leq 150$)가 주어진다.

이어지는 $M$개의 줄에는 각각 사전에 있는 단어 하나가 주어진다. 이 단어들은 모두 길이가 최대 $N$이고 문자 a-z로 이루어진다. 사전에 있는 모든 단어는 서로 다르다.

길이가 $N$이면서 너무 덴마크어처럼 들리지 않는 단어의 수를 출력한다. 이 수는 매우 클 수 있으므로, 이를 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 예제에는 서로 다른 단어가 $26^3$개 있다. 이 경우 덴마크어 사전은 비어 있으므로, 금지되는 단어는 하나도 없다.