JOIN

 Problem Statement

Problem Statement for ParenthesisRemoval

### Problem Statement

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:

1. Remove the first opening parenthesis in s.
2. 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.)

### Definition

 Class: ParenthesisRemoval Method: countWays Parameters: String Returns: int Method signature: int countWays(String s) (be sure your method is public)

### Constraints

-s will have between 2 and 2,500 characters, inclusive.
-s will be a correct parentheses sequence.

### Examples

0)

 `"()()()()()"`
`Returns: 1`
 In each removal we have to choose the leftmost closing parenthesis.
1)

 `"(((())))"`
`Returns: 24`
 In each removal we can choose any closing parenthesis we want. Note that these count as distint choices, even though all choices lead to the same string. Thus, there are 4*3*2*1 = 24 different sequences of removals that change s into an empty string.
2)

 `"((()()()))"`
`Returns: 54`
 Below is one of the 54 possible sequences of removals. Remember that in each step we also remove the first opening parenthesis. Remove the fourth closing parenthesis: "(()()())" Remove the second closing parenthesis: "()(())" Remove the first closing parenthesis: "(())" Remove the second closing parenthesis: "()" Remove the first closing parenthesis: ""
3)

 `"(())(())(())"`
`Returns: 8`
4)

 `"((((())((((((((((()((((((()))))())))))()))))))))))"`
`Returns: 948334170`