Anuj is very good at solving problems (actually he is not!). As his room mate Sachil has also heard the rumour, he tests his skills by giving him a problem.
His problem consists of a sequence S that consists of round brackets (characters "(" and ")" (without quotes)). Now, he explains to Anuj that a sequence of length n is called "Cool sequence" if it satisfies following conditions-
- It consists only of round brackets.
- It is not empty (that is n ≠ 0).
- The length of the sequence is even.
- First n/2 characters of the sequence are equal to "(".
- Last n/2 characters of the sequence are equal to ")".
For example, the sequence "((()))" is a cool sequence but the sequences "((())" and "(()())" are not.
Now, Sachil asks Anuj that for his given sequence S, how many of it's subsequences are "Cool". Note that a subsequence of s is a string that can be obtained from s by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.
Because the answer can be very big, he asks Anuj to find the answer modulo 10^9 + 7.
Anuj thought of the solution for a very long time, but he still doesn't know how to solve it. Help Anuj to solve this task and write a program that finds the answer for it!
CONSTRAINTS-
1 <= T <= 10
1 <= length(S) <= 10^5
INPUT-
First line of input consists of T, number of test cases.
Then, T cases follows and each of them consists of a single line that contains a string S, the bracket sequence.The string consists only of characters "(" and ")" (without quotes).
It's guaranteed that the string is not empty and its length doesn't exceed 100,000.
OUTPUT-
Output consists of T lines, each of them consists of answer for its corresponding case.
In the first sample the following subsequences are possible:
If we delete characters at the positions 1 and 5 (numbering starts with one), we will get the subsequence "(())".
If we delete characters at the positions 1, 2, 3 and 4, we will get the subsequence "()".
If we delete characters at the positions 1, 2, 4 and 5, we will get the subsequence "()".
If we delete characters at the positions 1, 2, 5 and 6, we will get the subsequence "()".
If we delete characters at the positions 1, 3, 4 and 5, we will get the subsequence "()".
If we delete characters at the positions 1, 3, 5 and 6, we will get the subsequence "()".
The rest of the subsequnces are not "Cool". So we got 6 distinct subsequences that are "Cool", so the answer is 6.
