← 返回题目列表

Codeforces · 629/C

C. 家庭门和支架

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

随着 Famil Door 的生日即将到来,他的一些朋友(例如 Gabi)决定给他买一份礼物。他的朋友们打算买一根由圆括号组成的字符串,因为 Famil Door 比任何其他字符串更喜欢长度为 n 的括号字符串!

圆括号序列被称为有效当且仅当:

1. 左括号总数等于右括号总数;
2. 对于序列的任何前缀,左括号的数量大于或等于右括号的数量。

Gabi 购买了一个长度为 m (m ≤ n) 的字符串 s,并希望完成它以获得长度为 n 的有效括号序列。他将选取一些由圆括号组成的字符串 p 和 q 并将它们合并为一个字符串 p + s + q,即将字符串 p 添加到字符串 s 的开头,将字符串 q 添加到字符串 s 的末尾。

现在他想知道,存在多少对字符串 p 和 q,使得字符串 p + s + q 是有效的圆括号序列。由于这个数字可能相当大,他想计算它对 109 + 7 的模。

输入

第一行包含 n 和 m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) – 分别是所需的字符串长度和 Gabi 购买的字符串长度。

第二行包含长度为 m 的字符串 s,仅由字符“(”和“)”组成。

输出

打印字符串 p 和 q 的对数,使得 p + s + q 是圆括号模 109 + 7 的有效序列。

示例

输入 #1

4 1
(

输出 #1

4

输入 #2

4 4
(())

输出 #2

1

输入 #3

4 3
(((

输出 #3

0

注意

在第一个示例中,有四个不同的有效对:

1. p = "(",q = "))"
2. p = "()", q = ")"
3. p = "", q = "())"
4. p = "", q = ")()"

在第二个示例中,获得所需字符串的唯一方法是选择空 p 和 q。

在第三个示例中,无法获得有效的括号序列。