Correct parentheses sequences can be defined recursively as follows:
- The empty string "" is a correct sequence.
- If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
- If "X" is a correct sequence, then "(X)" is a correct sequence.
- Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".
You are given a String s that is guaranteed to be a correct parentheses sequence.
A removal is an action that consists of two steps:
- Remove the first opening parenthesis in s.
- Remove one closing parenthesis in s. After you do so, s must again be a correct parentheses sequence.
Compute and return the number of distinct ways in which s can be reduced to an empty string by performing consecutive removals, modulo 10^9+7.
Two ways are considered distinct if there is a step in which you remove a different closing parenthesis.
(See Example 1 for clarification.)