Consider a string S of n characters '(', ')', and '?'. Your task is to replace each character '?' with either ')' or '('. Determine the number of Regular Bracket Sequences (RBS) that is possible after these replacements.
A bracket sequence is called regular if it is possible to obtain correct arithmetic expressions by inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and «(()(()))» are regular, whereas «)(», «(()» and «(()))(» are not.
Input format
- The first line contains one integer T denoting the number of test cases.
- The first line of each test case contains an integer n that denotes the length of string S.
- The second line of each test case contains a string that denotes the string S.
Output format
For each test case, print the number of RBS modulo 1e9+7 in a new line.
Constraints
1≤T≤1001≤n≤1000
The sum of n over T test cases does not exceed 1000.
For the first testcase, only 2 RBS are possible (()) and ()().
For the second testcase, the only possible RBS is ()(()).
