题目内容

魔法师梅林掌握着一本古老的符文合成书。书中记载了若干合成规则，每条规则可以将序列中最前面的三个连续符文替换为一个新的符文。所有符文均由小写英文字母表示。

梅林对一个初始长度为 $n$ 的符文序列反复应用合成规则，每次都替换当前序列开头的三个符文，直到序列长度变为 $1$，最终得到了一个符文 $x$。然而，他不慎遗忘了最初的序列。

现在，给你合成规则表、最终符文 $x$ 以及初始序列的长度 $n$（保证为奇数），请你计算出在给定规则下，可能的最初序列有多少种不同的情况。

约束条件：

• 序列长度 $n$ 为奇数，且 $1 \le n \le 13$。
• 规则数量 $m$ 满足 $1 \le m \le 15$。
• 所有符文以及规则中的字符串均由小写英文字母构成。
• 规则中，被替换的部分长度固定为 $3$，替换后的符文长度为 $1$，且不存在重复的规则。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示初始序列的长度和合成规则的数量。 接下来 $m$ 行，每行包含两个由小写字母组成的字符串 $U$ 和 $V$，其中 $U$ 的长度为 $3$，$V$ 的长度为 $1$，表示一条规则：开头的 $U$ 可以被合成为 $V$。 最后一行包含一个字符 $x$，表示最终合成得到的符文。

输出描述

输出一个整数，表示满足条件的可能初始序列数量。

样例1

输入

1 2
abc d
efg h
d

输出

1

说明

初始序列长度 $n = 1$，已经无法进行任何合成操作，因此初始序列必须与最终字符相同，只有 1 种可能（即 d）。规则虽然存在，但不会被使用。

样例2

输入

3 2
abc e
abd e
e

输出

2

说明

最终字符为 e，长度为 $3$。根据规则 $\text{abc} \to \text{e}$ 和 $\text{abd} \to \text{e}$，可以将 e 反向展开，得到长度为 3 的两个串 abc 和 abd。这两个串的长度与要求一致，不能再继续展开。因此共有 2 种可能的初始序列。

样例3

输入

5 4
abc e
abd e
xya a
xyb b
e

输出

2

说明

最终字符为 e，长度 $n=5$。反向构造过程如下：

• 从 e 出发，根据规则 $\text{abc} \to \text{e}$ 和 $\text{abd} \to \text{e}$，得到两个长度为 3 的串 abc 和 abd。
• 对于 abc，其首字符为 a。规则中有 $\text{xya} \to \text{a}$，没有其他规则能产生 a。将 a 替换为 xya，并与尾部 bc 拼接，得到长度为 5 的串 xyabc。
• 对于 abd，首字符也是 a，同样应用规则 $\text{xya} \to \text{a}$，得到 xyabd。
• 规则 $\text{xyb} \to \text{b}$ 对应的是字符 b，而当前所有长度为 3 的串的首字符都是 a，因此该规则不会被使用。

最终得到两个长度为 5 的串 xyabc 和 xyabd，故答案为 2。

样例4

输入

3 1
abc d
e

输出

0

说明

最终字符为 e，但没有任何规则能产生 e，因此无法从 e 反向展开。长度为 3 的集合为空，答案为 0。