Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3217
Count the Derivations

Time Limit: 1 Second      Memory Limit: 32768 KB

A context-free 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 context-free grammar of a string wn, is a sequence of the form "w0, w1, ..., wn", where "w0" is a single nonterminals and "wn" 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 "wi" (0 <= i <= n - 1), then "wi+1" is derived. For a specified legal string in the language generated by a context-free grammar, there maybe more than one derivation for it.

Let's take the following context-free 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.


First line of the input file contains an positive integer T, number of the test cases. Then T non-empty 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 | Empty
that 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 context-free gramma, nor are they directly related to the actual context-free gramma used.


For each test case, output the number of derivations the corresponding parse tree can represent, mod by 1,000,000,007.

Sample Input


Sample Output


Author: JIAO, Xiantao
Source: ZOJ Monthly, June 2009
Submit    Status