Limak 是一只小北极熊。北极熊讨厌长绳子,因此喜欢压缩它们。您还应该知道,利马克太年轻了,他只知道英文字母表的前六个字母:“a”、“b”、“c”、“d”、“e”和“f”。
给您一组 q 种可能的操作。 Limak 可以按任何顺序执行它们,任何操作可以应用任意次。第 i 个操作由长度为 2 的字符串 ai 和长度为 1 的字符串 bi 描述。 q 个可能的操作中没有两个具有相同的字符串 ai。
当 Limak 有一个字符串 s 时,如果 s 的前两个字母与两个字母的字符串 ai 匹配,他可以对 s 执行第 i 次操作。执行第 i 个操作会删除 s 的前两个字母并在其中插入字符串 bi。请参阅注释部分以获取进一步说明。
您可能会注意到,执行操作会将字符串 s 的长度精确减少 1。此外,对于某些操作集,可能存在无法进一步压缩的字符串,因为前两个字母与任何 ai 都不匹配。
Limak 希望从一个长度为 n 的字符串开始,执行 n - 1 次操作,最终得到一个单字母字符串“a”。他可以通过多少种方式选择起始字符串来得到“a”?请记住,利马克只能使用他认识的字母。
输入
第一行包含两个整数 n 和 q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) - 初始字符串的长度和可用操作的数量。
接下来的 q 行描述了可能的操作。其中第 i 个包含两个字符串 ai 和 bi (|ai| = 2, |bi| = 1)。保证 i ≠ j 时 ai ≠ aj,并且所有 ai 和 bi 仅包含前 6 个小写英文字母。
输出
打印长度为 n 的字符串数量,Limak 仅通过应用输入中给出的操作即可将其转换为字符串“a”。
示例
输入 #1
3 5 ab a cc c ca a ee c ff d
输出 #1
4
输入 #2
2 8 af e dc d cc f bc b da b eb a bb b ff c
输出 #2
1
输入 #3
6 2 bb a ba a
输出 #3
0
注意
在第一个示例中,我们计算长度为 3 的初始字符串,从中 Limak 可以获得所需的字符串“a”。有 4 个这样的字符串:“abb”、“cab”、“cca”、“eea”。第一个 Limak 可以使用操作 1 进行两次压缩(将“ab”更改为单个“a”)。第一个操作会将“abb”更改为“ab”,第二个操作会将“ab”更改为“a”。
其他三个字符串可以压缩如下:
- “出租车”$$\rightarrow$$“ab”$$\rightarrow$$“a”
- “cca”$$\rightarrow$$“ca”$$\rightarrow$$“a”
- “eea”$$\rightarrow$$“ca”$$\rightarrow$$“a”
在第二个示例中,唯一正确的初始字符串是“eb”,因为它可以立即压缩为“a”。