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

The sum of $$n$$ over $$T$$ test cases does not exceed 1000.