Problem Description

Given a bracket sequence, you need to add as few brackets as possible to make the sequence valid. After finishing the additions, there can be different resulting sequences. Please determine how many essentially different resulting sequences there are. Two results are essentially different if there exists some position where one result has a left bracket while the other result has a right bracket.

For example, for the bracket sequence (((), you only need to add two brackets to make it valid. There are the following different addition results: ()()() , ()(()), (())(), (()()), and ((())).

Input Format

Input one line containing a string $s$, representing the given bracket sequence. The sequence contains only left brackets and right brackets.

Output Format

Output one integer representing the answer. The answer may be very large, so please output the remainder of the answer modulo $1000000007$ (i.e., $10^{9}+7$).

((()

5

Hint

For $40\%$ of the testdata, $|s| \leq 200$.

For all testdata, $1 \leq |s| \leq 5000$.

Lanqiao Cup 2021, First Round Provincial Contest, Group A, Problem I (Group B, Problem J).

Translated by ChatGPT 5