CF629C Famil Door and Brackets

随着 Famil Door 的生日即将到来，他的一些朋友（如 Gabi）决定为他买一份礼物。他的朋友们打算买一个由圆括号组成的字符串，因为 Famil Door 特别喜欢长度为 $n$ 的括号字符串！ 一个圆括号序列被称为“合法”，当且仅当： 1. 左括号的总数等于右括号的总数； 2. 对于序列的任意前缀，左括号的数量都大于等于右括号的数量。 Gabi 买了一个长度为 $m$（$m\leq n$）的字符串 $s$，并希望将它补全，使其成为一个长度为 $n$ 的合法括号序列。他打算选择一些由圆括号组成的字符串 $p$ 和 $q$，并将它们与 $s$ 合并得到字符串 $p+s+q$，即在 $s$ 前面加上字符串 $p$，在 $s$ 后面加上字符串 $q$。 现在他想知道，有多少对字符串 $p$ 和 $q$ 可以使 $p+s+q$ 成为一个合法的圆括号序列。由于这个数量可能非常大，他希望你将答案对 $10^{9}+7$ 取模后输出。

第一行包含两个整数 $n$ 和 $m$（$1\leq m\leq n \leq 100000,\, n-m\leq 2000$）——期望的字符串长度和 Gabi 买到的字符串长度。 第二行包含一个长度为 $m$ 的字符串 $s$，只包含字符 '(' 和 ')'。

输出可以使 $p+s+q$ 成为一个合法圆括号序列的 $(p, q)$ 对的数量，对 $10^9+7$ 取模。

在第一个样例中，有四种不同的合法 $(p, q)$ 组合： 1. $p=$"(", $q=$"))" 2. $p=$"()", $q=$")" 3. $p=$"", $q=$"())" 4. $p=$"", $q=$")()" 在第二个样例中，唯一的办法是选择空的 $p$ 和 $q$。 在第三个样例中，没有办法得到合法的括号序列。 由 ChatGPT 5 翻译