给你一个括号序列$$$s$$$(不一定是常规的)。括号序列是仅包含字符“(”和“)”的字符串。
常规括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如,括号序列“()()”和“(())”是正规的(结果表达式是:“(1)+(1)”和“((1+1)+1)”),而“)(”、“(”和“)”则不是。
您的问题是计算长度为 $$$2n$$$ 的常规括号序列的数量,其中包含给定括号序列 $$$s$$$ 作为子字符串(连续字符序列)模 $$$10^9+7$$$ ($$$1000000007$$$)。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 生成的常规括号序列的一半长度(生成的序列的长度必须等于 $$$2n$$$)。
输入的第二行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 200$$$) — 字符串 $$$s$$$ 应该是每个生成的常规括号序列中的子字符串($$$|s|$$$ 是 $$$s$$$ 的长度)。
输出
仅打印一个整数 — 包含给定括号序列 $$$s$$$ 作为子字符串的常规括号序列的数量。由于这个数字可能很大,因此将其打印为 $$$10^9+7$$$ 模 ($$$1000000007$$$)。
示例
输入 #1
5 ()))()
输出 #1
5
输入 #2
3 (()
输出 #2
4
输入 #3
2 (((
输出 #3
0
注意
第一个示例满足上述条件的所有常规括号序列:
- "(((()))())";
- "((()()))()";
- "((()))()()";
- "(()(()))()";
- "()((()))()".
满足第二个示例上述条件的所有常规括号序列:
- "((()))";
- "(()())";
- "(())()";
- "()(())".
并且在第三个示例中不存在长度 $$$4$$$ 包含“(((”作为子字符串的常规括号序列。