Полярный медвежонок Лимак терпеть не может длинные строки, поэтому предпочитает сжимать их. К тому же он ещё маленький и знает только первые шесть букв английского алфавита: 'a', 'b', 'c', 'd', 'e' и 'f'.
Имеется q операций сжатия строк. Операции можно применять в любом порядке и каждую можно применить произвольное количество раз. Операция с номером i задаётся строкой ai длины два и строкой bi длины один. Все строки ai различны.
Если у Лимака есть строка s, то он может применить к ней i-ю операцию, только если первые два символа этой строки совпадают со строкой ai. Применение операции заключается в отбрасывании этих двух символов и приписывании в начало строки bi. Для пояснения посмотрите примечание.
Несложно заметить, что применение любой операции уменьшает длину строки s ровно на 1. Также для некоторых наборов операций возможно существование строки, сжатие которой невозможно, потому что первые две буквы не совпадают ни с одной из строк ai.
Лимак хочет начать со строки длины n и применить n - 1 операцию, чтобы в итоге получить строку «a». Сколько существует подходящих строк, из которых можно получить «a»? Не забывайте, что Лимак может использовать только те буквы, которые ему знакомы.
В первой строке записаны два числа n и q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) — начальная длина строки и количество доступных операций соответственно.
В следующих q строках даны описания операций. В i-й из них записаны строки ai и bi (|ai| = 2, |bi| = 1). Гарантируется, что ai ≠ aj для всех i ≠ j и что все ai и bi состоят только из первых шести строчных букв английского алфавита.
Выведите количество строк длины n, таких что Лимак сможет перевести в строку «a», используя только имеющиеся q операций.
3 5
ab a
cc c
ca a
ee c
ff d
4
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c
1
6 2
bb a
ba a
0
В первом примере существует 4 строки длины 3, из которых Лимак сможет получить строку «a»: "abb", "cab", "cca", "eea".
Для сжатия первой строки Лимаку достаточно два раза применить первую операций (замена «ab» на «a»). Первое применение превратит строку «abb» в «ab», а второе превратит «ab» в «a».
Остальные строки можно превратить в «a» следующим образом:
- "cab"
"ab" "a" - "cca" "ca" "a"
- "eea" "ca" "a"
Во втором примере единственной подходящей строкой является «eb».
