解题思路

题意简化一下：

• 有很多规则：U -> V，其中 U 是长度为 3 的字符串，V 是长度为 1 的字符。
• 每一次操作：只能把当前串“开头的 3 个字符”替换成一个字符。 也就是： 若当前串为 S = U + suffix，并且有规则 U -> V，那么可以把 S 变成 V + suffix。
• 已知：

题目内容

小明热表于研究字符替换。他拥有一张字符替换表，表上的每一条替换规则形如:将字符串串首的三个连续字符用某个单字符替换。一张替换表示例如下:

$\begin{array}{|c|c|c|} \hline \text { 规则编号 } & \text { 替换前 } & \text { 替换后 } \\ \hline 1 & a b d & e \\ \hline 2 & b c d & e \\ \hline 3 & a b a & b \\ \hline 4 & a b a & a \\ \hline \end{array}$

利用这张替换表，我们就可以对一个字符串进行字符替换了。例如，对于字符串 $ababacd$ 就可以通过如下操作替换成 $e$ 。

一天，小明利用他新研究出的字符替换表将一个长为 $n$ 的字符串 $S$ 替换成了一个单字符 $x$ 在那之后，他睡了一觉，等到醒来的时候， $S$ 竟然遗失了。

小明想知道，在已知字符替换表和单字符 $x$ 的情况下，$S$ 有多少种不同的可能?

输入描述

第一行两个正整数 $n,m$ ,分别表示 $S$ 的长度和字符替换表中的规则数量。保证 $n$ 为奇数。

接下来 $m$ 行，每一行两个字符串 $U,V$ ,表示一条替换规则($U$ 替换成 $V$ ).保证 $U$ 长度为 $3$ ，$V$ 长度为 $1$ 。保证不会有完全相同的两条替换规则(即不存在 $i,j(i≠j)$ 同时满足 $U_i=U_j$ 和 $V_i=V_j$).

接下来一行一个字符 $x$ ,表示经过替换最终得到的单字符。

对于本题中出现的所有字符/字符串(包括 $U，V,x$)，保证它们仅由小写英文字母组成。

$1≤n≤ 13,1 ≤ m ≤ 15$,且 $n$ 为奇数。

输出描述

样例1

输入

7 4
abd e
bcd e
aba b
aba a
e

输出

2

说明