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.
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)$.
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.