Chomsky Normal Form Grammar

A context free grammar is given in Chomsky Normal Form (CNF). Such a grammar consists of the following.

• a set $N$ of nonterminal symbols
• a set $T$ of terminal symbols
• a start symbol $S$ that belongs to $N$
• a set $R$ of rules of the form $A \to BC$ or $A \to a$, where $A, B, C \in N$ and $a \in T$

For $A \in N$, the language $L(A)$ generated by $A$ is defined as follows.

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

The language generated by the grammar is the language of the start symbol, $L(S)$. Given a string $x$, decide whether $x$ belongs to $L(S)$.

The first line contains the string $x$. It consists of lowercase letters only and its length is between 1 and 1000.

From the second line to the end of the file, each line holds one grammar rule. Nonterminal symbols are written as uppercase letters and terminal symbols as lowercase letters. A line ABC of length 3 means the rule $A \to BC$, and a line Aa of length 2 means the rule $A \to a$. The start symbol is always S. At least one rule is given, and the same rule can appear more than once.

Print 1 on one line if $x$ belongs to the language generated by the grammar, and 0 otherwise.