Country

在获得 IOI $2011$ 金牌后，gaoxin 发表了一篇包含大量重复语句的获奖感言。为了描述这类具有重复结构的发言，可以使用若干字符串名递归定义字符串。

字符串由小写英文字母组成，例如 a；字符串名由单个大写英文字母表示，例如 A。每个字符串名可以被定义为一系列大写或小写英文字母的连接，其中大写字母表示另一个字符串名，小写字母表示字符串中的实际字符。

例如，可以进行如下定义：

• A=greatglorycorrect
• B=xx
• C=leadusgo
• D=ABC
• E=DDDDdjh
• F=EEEEEgoodbye

不断展开定义中的字符串名，即可得到每个字符串名所表示的完整字符串。所有定义保证无环，因此展开过程一定能够结束。

其中有一个指定的字符串名，表示某人的完整发言。给定一个仅由小写字母组成的查询字符串，请计算它在完整发言中出现了多少次。

输入格式

第一行包含一个整数 $N$，表示字符串名的数量。

第二行包含一个大写英文字母 $F$，表示完整发言对应的字符串名。

接下来 $N$ 行，每行包含一个字符串定义。等号左侧是一个大写英文字母，表示字符串名；等号右侧由若干大写或小写英文字母组成，表示该字符串名的内容。

最后一行包含一个仅由小写英文字母组成的字符串，表示需要统计出现次数的查询字符串。

输出格式

输出一行一个整数，表示查询字符串在完整发言中的出现次数对 $10^4$ 取模后的结果。

样例输入

6
F
A=greatglorycorrect
B=xx
C=leadusgo
D=ABC
E=DDDDdjh
F=EEEEEgoodbye
g

样例输出

61

数据范围

• 对于全部数据，$N\le 26$；
• 每条字符串定义的长度不超过 $100$；
• 查询字符串的长度不超过 $100$；
• 所有字符串定义均无环。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

6
F
A=greatglorycorrect
B=xx
C=leadusgo
D=ABC
E=DDDDdjh
F=EEEEEgoodbye
g

输出

61