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 10⁹ + 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

5 3
abc
dd
xyz

11809073