Jaś i jego klawiatura

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Jaś chce ustawić hasło do swojego komputera, by mama nie przychodziła do niego i nie grała w pasjansa. Chce, by to hasło miało dokładnie n znaków. Dodatkowo, Jaś ma lekko niedziałającą klawiaturę. Po pierwsze, można wprowadzać nią tylko małe litery alfabetu angielskiego. Po drugie, dla pewnych par literek (L1, L2), zaraz po naciśnięciu L1 nie można nacisnąć L2, gdyż inaczej klawiatura zaczyna piszczeć. Ile różnych haseł Jaś może ustawić? Podaj odpowiedź modulo 123456789.

Wejście

W pierwszej linii jest liczba 1 <= n <= 30 000, oznaczająca liczbę liter w haśle, oraz liczba 0 <= k <= 676, oznaczająca liczbę różnych par (L1, L2), które nie mogą wystąpić po sobie w haśle. Kolejne k linii zawiera po dwie małe litery alfabetu angielskiego, oddzielone spacją - L1 i L2.

Wyjście

Wypisz jedną liczbę, oznaczającą liczbę różnych haseł, modulo 123456789.

Przykład

Dla wejścia:

4 4
a b
b c
c a
f g

prawidłową odpowiedzią jest:

449033