Problem description
Jasio dostał na prezent długopis (z logiem Januszex S.A. oczywiście). Bardzo ucieszył się z tego prezentu i postanowił napisać N–znakowy napis. Najpierw chciał napisać przypadkowy ciąg małych liter alfabetu angielskiego, ale teraz zaczął obawiać się, że w takim napisie znajdzie się jako spójny fragment jakiś wulgaryzm. Jasio nie wybaczyłby sobie tego. Zastanawia się ile różnych N–znakowych napisów bez wulgaryzmów może napisać. Pomóż mu!
Napisz program, który: wczyta listę wulgaryzmów oraz długość napisu, który chce napisać Jasio, wyznaczy liczbę napisów, które nie zawierają wulgaryzmów i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem i określające kolejno: długość napisu, który chce napisać Jasio oraz liczbę wulgaryzmów. W kolejnych M wierszach znajduje się lista wulgaryzmów, po jednym w wierszu. Każdy wulgaryzm jest niepustym ciągiem małych liter alfabetu angielskiego.
Wulgaryzmy podane na wejściu są parami różne.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – reszta z dzielenia przez 109 + 7 liczby napisów, które może napisać Jasio.
Ograniczenia
1 ≤ N ≤ 100, 0 ≤ M ≤ 10 000.
Długość pojedynczego wulgaryzmu nie przekracza 10 znaków, zaś łączna długość wszystkich wulgaryzmów nie przekracza 50 000 znaków.
Przykład
| Wejście | Wyjście | |
|
|