CF653B.Bear and Compressing

Limak is a little polar bear. Polar bears hate long strings and thus they like to compress them. You should also know that Limak is so young that he knows only first six letters of the English alphabet: 'a', 'b', 'c', 'd', 'e' and 'f'.

You are given a set of q possible operations. Limak can perform them in any order, any operation may be applied any number of times. The i-th operation is described by a string a__i of length two and a string b__i of length one. No two of q possible operations have the same string a__i.

When Limak has a string s he can perform the i-th operation on s if the first two letters of s match a two-letter string a__i. Performing the i-th operation removes first two letters of s and inserts there a string b__i. See the notes section for further clarification.

You may note that performing an operation decreases the length of a string s exactly by 1. Also, for some sets of operations there may be a string that cannot be compressed any further, because the first two letters don't match any a__i.

Limak wants to start with a string of length n and perform n - 1 operations to finally get a one-letter string "a". In how many ways can he choose the starting string to be able to get "a"? Remember that Limak can use only letters he knows.

Limak 是一只小北极熊。北极熊讨厌长字符串，因此它们喜欢压缩字符串。你还需要知道，Limak 年纪尚小，仅认识英文字母表的前六个字母：'a'、'b'、'c'、'd'、'e' 和 'f'。

给定一组共 $q$ 个可能的操作。Limak 可以以任意顺序执行这些操作，且每个操作均可执行任意多次。第 $i$ 个操作由一个长度为二的字符串 $a_i$ 和一个长度为一的字符串 $b_i$ 描述。在全部 $q$ 个可能的操作中，不存在两个操作具有相同的字符串 $a_i$。

当 Limak 拥有一个字符串 $s$ 时，若 $s$ 的前两个字母恰好匹配某个两字母字符串 $a_i$，则他可以在 $s$ 上执行第 $i$ 个操作。执行第 $i$ 个操作会将 $s$ 的前两个字母删除，并在该位置插入字符串 $b_i$。更多细节请参见“注释”部分。

你可能注意到，每次执行操作都会使字符串 $s$ 的长度恰好减少 1。此外，对于某些操作集合，可能存在一些字符串已无法继续压缩，因为其前两个字母不匹配任何一个 $a_i$。

Limak 希望从一个长度为 $n$ 的字符串出发，执行 $n-1$ 次操作，最终得到单字母字符串 "a"。有多少种方式可以选择初始字符串，使得 Limak 能够成功得到 "a"？请注意，Limak 只能使用他所认识的字母。

The first line contains two integers n and q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) — the length of the initial string and the number of available operations.

The next q lines describe the possible operations. The i-th of them contains two strings a__i and b__i (|a__i| = 2, |b__i| = 1). It's guaranteed that a__i ≠ a__j for i ≠ j and that all a__i and b__i consist of only first six lowercase English letters.

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 6$，$1 \leq q \leq 36$）—— 分别表示初始字符串的长度以及可用操作的数量。

接下来的 $q$ 行描述了所有可能的操作。其中第 $i$ 行包含两个字符串 $a_i$ 和 $b_i$（满足 $|a_i| = 2$，$|b_i| = 1$）。保证当 $i \neq j$ 时有 $a_i \neq a_j$，且所有 $a_i$ 和 $b_i$ 均仅由前六个小写英文字母组成。

Print the number of strings of length n that Limak will be able to transform to string "a" by applying only operations given in the input.

输出 Limak 能够通过仅应用输入中给出的操作，将长度为 n 的字符串变换为字符串 "a" 的字符串个数。

In the first sample, we count initial strings of length 3 from which Limak can get a required string "a". There are 4 such strings: "abb", "cab", "cca", "eea". The first one Limak can compress using operation 1 two times (changing "ab" to a single "a"). The first operation would change "abb" to "ab" and the second operation would change "ab" to "a".

Other three strings may be compressed as follows:

• "cab" "ab" "a"
• "cca" "ca" "a"
• "eea" "ca" "a"

In the second sample, the only correct initial string is "eb" because it can be immediately compressed to "a".

在第一个样例中，我们统计所有长度为 3 的初始字符串，使得 Limak 能够通过压缩操作得到目标字符串 "a"。满足条件的字符串共有 4 个："abb"、"cab"、"cca"、"eea"。对于第一个字符串 "abb"，Limak 可以连续两次使用操作 1（将子串 "ab" 替换为单个字符 "a"）进行压缩：第一次操作将 "abb" 变为 "ab"，第二次操作再将 "ab" 变为 "a"。

其余三个字符串的压缩过程如下：

• "cab" "ab" "a"
• "cca" "ca" "a"
• "eea" "ca" "a"

在第二个样例中，唯一满足条件的初始字符串是 "eb"，因为它可直接通过一次压缩操作变为 "a"。