Famil Door and Brackets

【题目描述】

Famil Door 的生日就要到了，Gabi（Famil Door的好朋友）想要给他买一个礼物。

Gabi 决定买一个只包含 '('、')' 的字符串，毕竟 Famil Door 最喜欢的字符串是长度为 $n$ 的只包含 '('、')' 的字符串。

我们称一个只包含 '('、')' 的字符串“有效”当且仅当：

'(' 的数量等于 ')' 的数量；对于该字符串的任意前缀，均满足 '(' 的数量大于等于 ')' 的数量；

Gabi 买了一个长度为 $m$ 的只包含 '('、')' 的字符串 $S$。

为了使它的长度达到 $n$ ，Gabi 要构造两个只包含 '('、')' 的字符串 $P,Q$，然后将 $P,S,Q$ 顺次连接得到字符串 $S′$ 。

给出 Gabi 买的字符串 $S$，要使 $S′$ 有效，Gabi 有多少种构造 $P,Q$ 的方案？（$P,Q$ 都可以为空）。

【输入格式】

第一行包括整数 $n,m$；第二行为长度为 $m$ 的字符串 $S$。

【输出格式】

输出一个正整数，表示构造 $P,Q$ 的方案数，答案对 $(10^9+7)$ 取模。

【样例输入1】

4 1
(

【样例输出1】

4

【样例输入2】

4 4
(())

【样例输出2】

1

【样例输入3】

4 3
(((

【样例输出3】

0

【样例说明】

在第一组样例中，有 $4$ 种不同的可行字符串对：

$p=$ "(", $q=$ "))"

$p=$ "()", $q=$ ")"

$p=$ "", $q=$ "())"

$p=$ "", $q=$ ")()"

在第二组样例中，唯一让 $S′$ 有效的方案是令 $p$ 和 $q$ 为空串。

在第三组样例中，没有一种方法能得到一个有效的字符串。

【数据规模与约定】

对于 30% 的数据，$1 \le m \le 5,1\le m \le n \le 20$

对于 100% 的数据，$1\le m\le n\le 100000,n−m\le 2000$

【来源】

Codeforces Round #343 Div.2 Problem C