Easy Sequence

Problem Description

soda has a string containing only two characters -- '(' and ')'. For every character in the string, soda wants to know the number of valid substrings which contain that character. Note: An empty string is valid. If $S$ is valid, $(S)$ is valid. If $U,V$ are valid, $UV$ is valid.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: A string $s$ consisting of '(' or ')' $(1 \le |s| \le 10^6)$.

Output

For each test case, output an integer $m =\displaystyle \sum_{i = 1}^{|s|} (i\cdot ans_i \text{ mod } 1000000007)$, where $ans_i$ is the number of valid substrings which contain $i$-th character.

Sample Input

2
()()
((()))

Sample Output

20
42

Hint

For the second case, $ans = \{1, 2, 3, 3, 2, 1\}$, then $m=1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 + 4 \cdot 3 + 5 \cdot 2 + 6 \cdot 1 = 42$

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6