题目描述

上下文无关文法由若干条推导规则组成，每条规则形如

<nonterminal> ::= <expression>

其中 <nonterminal> 是一个非终结符，<expression> 是由终结符和非终结符组成的非空符号序列，表示该非终结符可以被替换成这个表达式。

如果同一个非终结符有多条规则，例如

A ::= expr0
A ::= expr1
A ::= expr2

也可以写在同一行，用 | 分隔：

A ::= expr0 | expr1 | expr2

文法中有一个特殊的非终结符称为开始符号。从开始符号出发，经过若干次推导后能够得到的纯终结符串，就是该文法能够生成的单词。

本题中，大写字母 A 到 Z 只表示非终结符，小写字母 a 到 z 只表示终结符。

例如规则

A ::= BD
B ::= bB | b | Bb
D ::= dD
D ::= d

以 A 为开始符号时，可以生成一个或多个 b 后接一个或多个 d 的字符串，例如 bd、bbd、bddd、bbbddd 等。

一个解析树的根节点是开始符号。每个非终结符节点选择一条规则进行推导，它的孩子从左到右依次是该规则右侧表达式中的各个符号。终结符节点为叶子；按照从左到右的顺序读取所有叶子，得到被解析的单词。

同一个单词可能对应多棵不同的解析树。若两棵解析树的树结构不同，或者结构相同但至少一个对应的非终结符节点使用了不同的推导规则，则认为它们不同。因此，即使有两条内容完全相同的规则，选择不同的那一条也会形成不同的解析树。

为了避免出现无限多棵解析树，保证任意规则右侧的某个备选表达式都不会仅由一个大写字母构成。

给出全部规则、开始符号和目标单词，求该单词的不同解析树数量。如果数量超过 $10^9$，输出 -1。

输入格式

第一行包含一个整数 $R$ 和一个大写字母 seed，分别表示规则行数和开始符号。

接下来 $R$ 行，每行是一条规则。每行均为以下形式：

A ::= expression1 | expression2 | ...

最后一行输入目标单词 word。

输出格式

输出目标单词的不同解析树数量。如果数量超过 $10^9$，输出 -1。

数据范围

• $1\le |word|\le 35$，且 word 只包含小写字母；
• seed 为一个大写字母；
• $1\le R\le 50$；
• 每条规则的整行长度在 $1$ 到 $50$ 之间；
• 每行规则以一个大写字母开头，随后为字符串 ::=，再随后为一个或多个用 | 分隔的非空表达式；
• 每个表达式只包含大小写英文字母；
• 不存在只由一个大写字母组成的备选表达式。

样例 1

输入

4 A
A ::= BD
B ::= bB | b | Bb
D ::= dD
D ::= d
bdd

输出

1

样例 2

输入

4 A
A ::= BD
B ::= bB | b | Bb
D ::= dD
D ::= d
bbd

输出

2

样例 3

输入

4 A
A ::= BD
B ::= bB | b | Bb
D ::= dD
D ::= d
ddbb

输出

0

样例 4

输入

2 B
B ::= topcoder | topcoder
B ::= topcoder
topcoder

输出

3

样例 5

输入

5 X
A ::= BCD
Z ::= z
B ::= Cz | Dz | Zz
C ::= Bz | Dz
D ::= Cz | Bz
zzz

输出

0

样例 6

输入

1 B
B ::= bB | bB | bB | bB | b
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

输出

-1