
ZOJ Problem Set  3217
A contextfree grammar is a language generator. It is a formal system that describes a language by specifying how any legal string can be derived from a distinguished symbol. The grammar consist of a set of productions. A production is of the form "V ::= w", it states that the single symbol "V" can be replaced by a given string "w". Symbols that appear in the left hand side of productions are called nonterminals, and symbols that only appear in the right hand side of productions are called terminals. The right hand side of a production is a string of terminals and/or nonterminals (possibly empty). A derivation of a contextfree grammar of a string w_{n}, is a sequence of the form "w_{0}, w_{1}, ..., w_{n}", where "w_{0}" is a single nonterminals and "w_{n}" is a string of only terminals. The derivation has n steps. In each step, one production is selected and applied to one nonterminal in the string "w_{i}" (0 <= i <= n  1), then "w_{i+1}" is derived. For a specified legal string in the language generated by a contextfree grammar, there maybe more than one derivation for it. Let's take the following contextfree grammar, which generates balanced parentheses (e stands for empty symbol), as an example, there are ten different derivations to generate the string "(())()" from the start symbol "S", Actually each derivation can be represented by a parse tree, and some derivations may have a same parse tree representation. Coincidentally, all the ten derivations in our example can be represented by the following parse tree, we say the ten derivations are similar, because, informally, they represent applications of the same rules in the grammar at the same positions in the strings, only differing in the relative order of these applications. Now you are given a parse tree, please count how many similar derivations the parse tree can represent. Input First line of the input file contains an positive integer T, number of the test cases. Then T nonempty lines follow, each line is a parse tree representation. A parse tree is denoted by a string of the language of the following grammar, Tree ::= '(' Subtrees ')' Subtrees ::= Tree Subtrees  Emptythat is, trees have parentheses around them, and there are arbitrarily many (maybe none) subtrees inside. As an example, take a look at the tree in the figure above which is denoted in the sample input. The parse tree given will have at most 1,000 nodes. Note: the inputs are just descriptions of parse tree structures, they are not generated by our sample contextfree gramma, nor are they directly related to the actual contextfree gramma used. Output For each test case, output the number of derivations the corresponding parse tree can represent, mod by 1,000,000,007. Sample Input 1 ((()(()(())())())(()(())())) Sample Output 10 Author: JIAO, Xiantao Source: ZOJ Monthly, June 2009 