Bob 是形式语言课程中最优秀的学生之一。现在他正在学习乔姆斯基范式（Chomsky Normal Form, 简称 CNF）下的上下文无关文法。

一个此类文法由以下部分组成：

• 非终结符集合 $N$
• 终结符集合 $T$
• 一个特殊的非终结符，称为起始符号 $S$
• 一个规则集合 $R$，规则的形式为 $A \to BC$ 或 $A \to a$，其中 $A, B, C \in N$，$a \in T$。

对于 $A \in N$，我们定义由 $A$ 生成的语言 $L(A)$ 如下：

$$L(A) = \{ wz \mid w \in L(B), z \in L(C), \text{ 其中 } A \to BC \in R \} \cup \{ a \mid A \to a \in R \}$$

由起始符号为 $S$ 的文法所生成的语言定义为 $L(S)$。

Bob 必须解决以下问题：对于给定的 CNF 上下文无关文法和输入字符串 $x$，判断 $x$ 是否在文法生成的语言 $L(S)$ 中。

输入格式

输入数据从标准输入读取。

第一行包含输入字符串 $x$（$|x| \le 1000$）。

接下来是文法规则，每行一个，形式为 ABC（表示 $A \to BC$）或 Aa（表示 $A \to a$）。

我们认为起始符号总是 $S$。

输入数据是正确的，并以文件结束符（EOF）结束。

输出格式

如果字符串在文法生成的语言中，程序输出 1，否则输出 0。

程序将结果输出到标准输出，从行首开始。

样例

输入样例 1

a
SAB
Sa
Ab

输出样例 1

1

输入样例 2

ab
SAB
Sa
Ab

输出样例 2

0

输入样例 3

ab
SAB
Sa
Ab
Ba

输出样例 3

0

说明

共有三个测试样例。前两个使用相同的文法：SAB、Sa、Ab（即 $S \to AB$，$S \to a$，$A \to b$）。对于第一个测试，输入字符串为 a，结果为 1；而对于第二个测试，输入字符串为 ab，结果为 0。