题目内容

一位语言学家在考古现场发现了一套古老的符号归约系统。在这个系统中，存在若干条规则，每条规则可以将一个由三个小写字母组成的串压缩成单个小写字母。形式化地说，一条规则由长度为 $3$ 的串 $U$ 和长度为 $1$ 的字符 $V$ 组成，表示 $U$ 可以被替换为 $V$。

对于一个初始字母序列 $S$，你可以反复进行下列操作：只要 $S$ 的长度大于 $1$，就取出 $S$ 最左侧的三个连续字符，如果存在某条规则允许将这三个字符替换为某个字符，则进行替换；此时 $S$ 的长度将减少 $2$。若经过若干次操作后，$S$ 恰好变为单独一个字符 $c$，则称 $S$ 可以归约到 $c$。

现在给出全部归约规则以及最终得到的字符 $c$，但最初的序列 $S$ 已经丢失。已知 $S$ 的长度为 $n$，你需要计算有多少种不同的初始序列 $S$ 能够归约到 $c$。

数据范围：长度 $n$ 为奇数且满足 $1 \le n \le 13$；规则条数 $m$ 满足 $1 \le m \le 15$。保证所有出现的字符串和字符均由小写字母构成，且不存在两条完全相同的规则。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示初始序列的长度和规则条数。保证 $n$ 为奇数，$1 \le n \le 13$，$1 \le m \le 15$。 接下来 $m$ 行，每行包含两个由空格分隔的字符串 $U$ 和 $V$，其中 $U$ 的长度为 $3$，$V$ 的长度为 $1$，表示一条从 $U$ 到 $V$ 的归约规则。 最后一行包含一个字符 $c$，表示归约最终得到的字符。

输出描述

输出一个整数，表示长度为 $n$ 且能够归约到字符 $c$ 的不同初始序列的数量。

样例1

输入

1 2
abc d
xyz e
d

输出

1

说明

初始序列长度 $n=1$，无需任何归约操作。序列能够归约到字符 d 当且仅当序列本身恰好为 d。尽管存在两条规则，但在长度为 1 的情况下不会被执行。因此只有 1 种初始序列（即 "d"）满足条件。

样例2

输入

3 3
abc x
def x
ghi y
x

输出

2

说明

初始序列长度 $n=3$，恰好可以进行一次归约。要使归约结果为 x，必须存在一条规则直接将整个序列替换为 x。规则中 "abc" $\to$ x 和 "def" $\to$ x 满足条件，而 "ghi" $\to$ y 不能得到 x。因此可能的初始序列为 "abc" 和 "def"，共 2 种。

样例3

输入

5 4
abc d
aaa d
deb x
ddd y
x

输出

2

说明

长度为 5 的序列归约到 x 需要经过两次替换。最后一次归约必须将某长度为 3 的串变为 x，由规则 "deb" $\to$ x 可知该串为 "deb"。

倒数第二次归约需将序列最左侧三个字符替换为 d，从而与剩余字符 "eb" 拼接得到 "deb"。规则中能产生 d 的有 "abc" $\to$ d 和 "aaa" $\to$ d，因此初始序列只可能是 "abc" + "eb" = "abceb" 或 "aaa" + "eb" = "aaaeb"，共 2 种。

样例4

输入

7 5
abc d
def e
efg z
xyz d
aaa b
z

输出

2

说明

从最终字符 z 出发反向构造。长度为 3 的串只能是 "efg"（规则 "efg" $\to$ z）。将 "efg" 的首字符 e 反向展开：规则 "def" $\to$ e，得到长度为 5 的串 "def" + "fg" = "deffg"。

再将 "deffg" 的首字符 d 反向展开：规则 "abc" $\to$ d 和 "xyz" $\to$ d，得到长度为 7 的串 "abceffg" 和 "xyzeffg"。规则 "aaa" $\to$ b 在此过程中未被使用。因此共有 2 种初始序列。