Problem F
Danska

Boschua ska flytta till Lund för att studera vid LTH. Du har fått reda på att Lund ligger i Skåne, och nu är du orolig att Boschua ska börja låta dansk.

För att förhindra detta vill du visa Boschua hur många ord som inte alls låter danska. Enligt dig låter ett ord danskt om det innehåller minst ett ord från den danska ordboken. Tyvärr äger du inte den officiella danska ordboken, men den gamla ordboken du hittade i källaren får duga.

Exempelvis, anta att orboken endast innehåller ordet knallert. Då anser du att ordet husknallertrumma låter danskt eftersom det innehåller ordet knallert. Däremot anser du att ordet knallerunt inte låter danskt eftersom det inte innehåller knallert.

Figure 1: Ordet husknallertrumma låter danskt.

Figure 2: Ordet knallerunt låter inte danskt.

Du inser snabbt att det finns för många ord som inte låter danska för att skriva ner dem alla. Därför tänker du att det räcker med att räkna antalet ord som inte låter danska och berätta det för Boschua. Även detta visar sig vara svårt, eftersom det finns så många ord som inte låter danska.

Till slut nöjer du dig med att räkna antalet ord som består av endast små engelska bokstäver a-z, har exakt $N$ bokstäver och inte låter danska. Ett ord låter för danskt ifall ordet innehåller minst ett ord från ordboken som en delsträng.

Indata

Den första raden i indatan innehåller heltalen $N$ ($1 \le N \le 100$) och $M$ ($0 \le M \le 150$), längden på orden vi betraktar och antalet ord i ordboken.

Därefter följer $M$ rader, där varje rad innehåller ett ord från ordboken. Alla dessa orden har längd som mest $N$ och består av bokstäver a-z. Alla dessa orden är dessutom unika.

Utdata

Skriv ut antalet ord av längd $N$ som inte låter för danskt. Eftersom detta talet kan bli väldigt stort, skriv ut det modulo $10^9+7$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

I första fallet finns det $26^3$ olika ord. Eftersom den Danska ordboken är tom i detta fallet förbjuds inga av dessa.

3 0

17576

2 2
a
po

624

5 5
java
py
js
rust
apl

11738952