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:</p>

• 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), z ∈ 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).

입력 형식

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. </p>

The input data are correct and terminate with an end of file. The program prints the result to the standard output from the beginning of a line. 

출력 형식

The program prints 1 if the string is in the language generated by the grammar, 0 otherwise.

예제 입력 1

a
SAB
Sa
Ab

예제 출력 1

1

예제 입력 2

ab
SAB
Sa
Ab

예제 출력 2

0

예제 입력 3

ab
SAB
Sa
Ab
Ba

예제 출력 3

0

힌트

Input/output samples are given in the table below. There are three tests. The first two use the same grammar: SAB, Sa, Ab (S→AB, S→a, A→b). For the first test the input string is a, and the result is 1, while for the second test the input string is ab and the result is 0.