G :: Grammar

Time Limit: 10 Seconds Memory Limit: 131072 KB

Bob is one of the best students of the Formal Languages class. Now he is learning about context free grammars in the Chomsky Normal Form (CNF). Such a grammar consists of:

a set of nonterminal symbols N

a set of terminal symbols T

a special nonterminal symbol, called the start symbol S

a set R of rules of the form A -> BC or A -> a, where A, B, C ∈ N, a ∈ T.

If A ∈ N, we define L(A), the language generated by A, as follows:

L(A) = { wz | w ∈ L(B), ∈ L(C), where A -> BC ∈ R } ∪ { a | A -> a ∈ R }.

The language generated by the grammar with start symbol S is defined to be L(S).

Bob must solve the following problem: for a given context free grammar in CNF, on input string x,

determine whether x is in the language generated by the grammar, L(S).

Input

The program input is from a text file. It starts with the input string x (|x|<=1000). Follows the grammar rules, in the form ABC or Aa, each on a separate line. We consider that the start symbol is always S.

The input data are correct and terminate with an end of file.

Output

The program prints 1 if the string is in the language generated by the grammar, 0 otherwise.The program prints the result to the standard output from the beginning of a line.

Sample Input

a
SAB
Sa
Ab

ab
SAB
Sa
Ab

ab
SAB
Sa
Ab
Ba

Sample Output

Submit