← 返回题目列表

Codeforces · 1015/F

F. 括号子串

中文机器翻译题面 查看原题

给你一个括号序列$$$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$$$ 包含“(((”作为子字符串的常规括号序列。