Changu likes to play with string and subsequences. He has thought of a puzzle for you. Can you answer him?

He gives you a sequence of  '('  and  ')' . Your task is to find out the number of its different subsequences that are regular bracket sequences.

For example, the sequence “()()” has 3 such subsequences: “()()”, “()”,  and “”. As the number can be large, you have to output answer modulus 1000000007.

Input:

 The first line contains T, the number of test cases. T lines follow, each containing a sequence of '(' and ')'.

Output:

For each test case, print the requires answer.

Sample Input:

2

()

()()

Sample Output:

2

3

Constraints:

T<10

0<|S|<1000