408103: GYM102985 J Chang's Capricious Cupcakes

Chang has received a request to decorate an enormous amount of cupcakes for an upcoming wedding reception. The bride and groom are both programmers, so he decides to theme his frosting around balanced parentheses sequences. We can define balanced parentheses sequences as follows:

• $$$e$$$ (the empty string) is a balanced bracket sequence.
• If $$$s$$$ is a balanced bracket sequence, then so is $$$(s)$$$.
• If $$$s$$$ and $$$t$$$ are balanced bracket sequences, then so is $$$st$$$.

The planned arrangement of Chang's cupcakes is a line of frosted opening and closing parentheses (one symbol per cupcake) such that the created bracket sequence is balanced. Although the cupcakes are already baked, Chang does not have time to frost all the cupcakes by himself before the wedding due to prior commitments. Chen, his eager assistant, offers to frost a prefix of the cupcakes and create instructions for the rest of the cupcakes for Chang to frost upon returning.

Unfortunately, Chen forgot to leave Chang the intended finished sequence, and it is the day of the wedding! Chang does not perform well with indecision, and wants to know the number of different ways he can finish frosting the remaining cupcakes with $$$($$$ and $$$)$$$ such that a balanced bracket sequence is still created. Help Chang calculate the number of options he has for finishing frosting the cupcakes!

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$), the total number of cupcakes. The second line of input contains a string $$$s$$$ of left and right parentheses representing the prefix of cupcakes already frosted. This prefix has length at most $$$N$$$ and is not an empty string.

Output a single integer representing the number of ways Chang can frost the remaining cupcakes modulo $$$10^9+7$$$.

6
(()

2

4
((

1