Bracket Substring

Description:

Input:

The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the half-length of the resulting regular bracket sequences (the resulting sequences must have length equal to $$$2n$$$).

The second line of the input contains one string $$$s$$$ ($$$1 \le |s| \le 200$$$) — the string $$$s$$$ that should be a substring in each of the resulting regular bracket sequences ($$$|s|$$$ is the length of $$$s$$$).

Output:

Print only one integer — the number of regular bracket sequences containing the given bracket sequence $$$s$$$ as a substring. Since this number can be huge, print it modulo $$$10^9+7$$$ ($$$1000000007$$$).

Sample Input:

5
()))()

Sample Output:

5

Sample Input:

3
(()

Sample Output:

4

Sample Input:

2
(((

Sample Output:

0

Note:

All regular bracket sequences satisfying the conditions above for the first example:

• "(((()))())";
• "((()()))()";
• "((()))()()";
• "(()(()))()";
• "()((()))()".

All regular bracket sequences satisfying the conditions above for the second example:

• "((()))";
• "(()())";
• "(())()";
• "()(())".

And there is no regular bracket sequences of length $$$4$$$ containing "(((" as a substring in the third example.