Description:
You are given a bracket sequence $$$s$$$ (not necessarily a regular one). A bracket sequence is a string containing only characters '(' and ')'.
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.
Your problem is to calculate the number of regular bracket sequences of length $$$2n$$$ containing the given bracket sequence $$$s$$$ as a substring (consecutive sequence of characters) modulo $$$10^9+7$$$ ($$$1000000007$$$).
Input Format:
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 Format:
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$$$).
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.