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 required answer.

Sample

Input
2
()
()()

Output:
2
3

Constraints

T < 10

0 < |S| <= 1000