Each test file starts with an integer ‘t’ — the number of testcases.

In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].

Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’

Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.

Duplicate strings are not allowed. The final expressions to be counted have to be distinct

As the answer may be large, please output it modulo 1000000007 (10^9+7)

Output one integer per line corresponding to each testcase.

Constraints :

1 <= t <= 20

1 <= n <= 100

0 <= Number of ‘*’ in the input string <= min(n,10)

Sample Input:

2

(*(*)*)

((**)*

Sample Output

5

9

Explanation

The five possible valid solutions are for the first input are :

((()))

()(())

()()()

(())()

(())

The nine possible valid solutions are for the second input are :

(((())))

(()(()))

(()()())

(()())

((()))

()(())

()()()

()()

(())