Problem Description

You are the speaker for the special lecture "Parentheses Sequence and Coloring". Today, you have decided to introduce a method for coloring a string $ S $ consisting only of ( and ). It is guaranteed that $ S $ has no contradiction in parentheses matching.

Consider coloring all characters in $ S $ either red or blue. If the ( at the $ i $th position and the ) at the $ j $th position correspond, then the substring $ S[i,j] $ must satisfy the condition that the number of red characters $ R $ and the number of blue characters $ B $ satisfy $|R-B| \leq K$.

Find the total number of valid coloring methods modulo $ 1,000,000,007 $.

In this problem, a string with no contradiction in parentheses matching is defined as follows:

1. An empty string has no contradiction in parentheses matching.
2. For strings $ A $ and $ B $ with no contradiction in parentheses matching, the concatenated string $ AB $ also has no contradiction in parentheses matching.
3. For a string $ A $ with no contradiction in parentheses matching, the string ($ A $) also has no contradiction in parentheses matching. The ( and ) at both ends are said to correspond.
4. Any string that does not satisfy any of the above conditions has a contradiction in parentheses matching.

Input Format

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

$ S $ $ K $

• The first line contains the parentheses sequence $S\ (2 \leq |S| \leq 3,000)$, which is guaranteed to have no contradiction in parentheses matching.
• The second line contains the integer $K(0 \leq K \leq 3,000)$, which represents the constraint for coloring.

Output Format

Output the total number of valid coloring methods modulo $ 1,000,000,007 $. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

()()
0

Sample Output #1

4

Sample Input #2

()()
2

Sample Output #2

16

Sample Input #3

(()())
2

Sample Output #3

50

Sample Input #4

()()()()()()()()()()()()()()()()
2

Sample Output #4

294967268

Notes/Hints

Partial Points

This problem has partial points:

• Correctly solving the dataset where $2 \leq |S| \leq 8$ will award $ 10 $ points.
• Correctly solving the dataset where $2 \leq |S| \leq 100$ will award an additional $ 10 $ points.
• Correctly solving the dataset without additional constraints will award an additional $ 50 $ points, totaling $ 70 $ points.

Sample Explanation 1

• The ( at the 1st position corresponds with the ) at the 2nd position, and the ( at the 3rd position corresponds with the ) at the 4th position.
• For convenience, let's represent red parentheses with <>, and blue parentheses with [].
• The answer is <]<], <][]>, []<], [][]>, totaling 4 ways.
• A coloring like <><] does not satisfy the constraint $|R-B| \leq K$ in $ S[1,2] $.
• This case satisfies the first partial point constraint.

Sample Explanation 2

• The answer is <><>, <><], <>[], <][]>, <]<>, <]<], <][], <][]>, []<>, []<], []<>, [][]>, []<>, []<], [][], [][]>, totaling 16 ways.
• This case satisfies the first partial point constraint.

Sample Explanation 3

• The ( at the 1st position corresponds with the ) at the 6th position, the ( at the 2nd position corresponds with the ) at the 3rd position, and the ( at the 4th position corresponds with the ) at the 5th position.
• This case satisfies the first partial point constraint.

Sample Explanation 4

• The total number of coloring methods is $ 4,294,967,296 $, but you should output the remainder when divided by $ 1,000,000,007 $, which is $ 294,967,268 $.
• This case satisfies the second partial point constraint.

见题面 Input 部分

见题面 Output 部分