Bracket Substring

题意翻译

　给你一个括号序列 $s$ （不一定是常规序列）。 括号序列是仅包含字符'（'和'）'的字符串。 　常规括号序列是一种特殊的括号序列，它可以通过在序列的原始字符之间插入字符“1”和“+”来转换为正确的算术表达式。 例如，括号序列“（）（）”和“（（））”是常规的（结果表达式为：“（1）+（1）”和“（（1 + 1）+1）”），以及 “）（”，“（”和“）”不是。 　你的问题是计算长度为 $2n$ 的常规括号序列的数量，而且必须满足给定括号序列 $s$ 是它的子串（连续字符序列）。输出这个数量模　 $10 ^ 9 + 7$ （1000000007）的结果。

题目描述

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 $ ).

输入输出格式

输入格式

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 $ ).

输出格式

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 $ ).

输入输出样例

输入样例 #1

5
()))()

输出样例 #1

5

输入样例 #2

3
(()

输出样例 #2

4

输入样例 #3

2
(((

输出样例 #3

0

说明

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.