Полярный медвежонок Лимак терпеть не может длинные строки, поэтому предпочитает сжимать их. К тому же он ещё маленький и знает только первые шесть букв английского алфавита: 'a', 'b', 'c', 'd', 'e' и 'f'.
Имеется q операций сжатия строк. Операции можно применять в любом порядке и каждую можно применить произвольное количество раз. Операция с номером i задаётся строкой ai длины два и строкой bi длины один. Все строки ai различны.
Если у Лимака есть строка s, то он может применить к ней i-ю операцию, только если первые два символа этой строки совпадают со строкой ai. Применение операции заключается в отбрасывании этих двух символов и приписывании в начало строки bi. Для пояснения посмотрите примечание.
Несложно заметить, что применение любой операции уменьшает длину строки s ровно на 1. Также для некоторых наборов операций возможно существование строки, сжатие которой невозможно, потому что первые две буквы не совпадают ни с одной из строк ai.
Лимак хочет начать со строки длины n и применить n - 1 операцию, чтобы в итоге получить строку «a». Сколько существует подходящих строк, из которых можно получить «a»? Не забывайте, что Лимак может использовать только те буквы, которые ему знакомы.
Выходные данные
Выведите количество строк длины n, таких что Лимак сможет перевести в строку «a», используя только имеющиеся q операций.
Примечание
В первом примере существует 4 строки длины 3, из которых Лимак сможет получить строку «a»: "abb", "cab", "cca", "eea".
Для сжатия первой строки Лимаку достаточно два раза применить первую операций (замена «ab» на «a»). Первое применение превратит строку «abb» в «ab», а второе превратит «ab» в «a».
Остальные строки можно превратить в «a» следующим образом:
- "cab"
"ab" "a" - "cca" "ca" "a"
- "eea" "ca" "a"
Во втором примере единственной подходящей строкой является «eb».