Problem Description

Niwango, a member of Dwango, loves strings with balanced parentheses. Today, he decided to play with rearranging a lot of parentheses.

Niwango has a string \( S \) of length \( N \) consisting only of ( and ). \( S \) contains an equal number of ( and ).

A sequence \( p \) is called a good sequence if:

• It can be obtained by permuting \( (1, 2, 3, ..., N) \)
• The string \( t \) formed by \( t_i = s_{p_i} \) is a balanced parentheses string

Calculate the inversion numbers for all good sequences and output the sum of these inversion numbers modulo \( 10^9 + 7 \).

The inversion number of a sequence \( p \) is defined as the number of pairs \( (i, j) \) such that \( p_i > p_j \). A balanced parentheses string is defined as follows:

1. The empty string is a balanced parentheses string.
2. If \( r \) is a balanced parentheses string, then the string obtained by concatenating (, \( r \), and ) in this order is also a balanced parentheses string.
3. The concatenation of two balanced parentheses strings is also a balanced parentheses string.
4. Only strings generated by the above rules are balanced parentheses strings.

Input Format

The input is given from the standard input in the following format:

\( N \) \( S \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2
)(

Sample Output #1

1

Sample Input #2

6
(())()

Sample Output #2

1060

Sample Input #3

16
)())()((((()))()

Sample Output #3

58589334

Notes/Hints

Constraints

• \( 2 \leq N \leq 5 \times 10^5 \)
• \( S \) consists only of ( and )
• \( S \) contains an equal number of ( and )
• \( |S| = N \)

Sample Explanation 1

The possible sequences for \( p \) are \( (1, 2) \) and \( (2, 1) \), corresponding to the strings )( and () respectively. The only good sequence is \( (2, 1) \), and its inversion number is \( 1 \).

Sample Explanation 3

• Remember to find the answer modulo \( 10^9 + 7 \)

见题面 Input 部分

见题面 Output 部分