Family Door 的生日就要到了，Gabi（Family Door的好朋友）想要给他买一个礼物。Gabi决定买一个只包含 '('、')' 的字符串，毕竟 Family Door 最喜欢的字符串是长度为 \(n\) 的只包含 '('、')' 的字符串。

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

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

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

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

\(1\leq m\leq n\leq 100000,n-m\leq 2000\)

---

水篇题解QAQ

显然可以分开考虑\(P,Q\)的方案，设\(f_{i,j}\)表示有\(i\)个\((\)，\(j\)个\()\)的方案数，这个可以很轻松的dp出来：

\[f_{i,j}=f_{i-1,j}+f_{i,j-1} \]

然后我们枚举\(P\)的\((,)\)的情况，多注意一下就是\(S\)中\()\)会比\((\)多，所以我们记下\(S\)中某个位置最多的\()\)比\((\)多的个数\(x\)，\(P\)中\((\)的个数就要比\()\)多\(x\)。

然后\(Q\)的情况就不用多dp了，\(j\)个\()\)，\(i\)个\((\)的方案数就是\(f_{i,j}\)。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e5;
const int M = 2e3;
const int p = 1e9 + 7;
using namespace std;
int n,m,f[M + 5][M + 5],sm1,sm2,ans,mx;
char ch[N + 5];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",ch + 1);
    if (n % 2 == 1)
    {
        cout<<0<<endl;
        return 0;
    }
    f[0][0] = 1;
    for (int i = 1;i <= M;i++)
    {
        f[i][0] = 1;
        for (int j = 1;j <= i;j++)
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % p;
    }
    for (int i = 1;i <= m;i++)
    {
        if (ch[i] == '(')
            sm1++;
        if (ch[i] == ')')
            sm2++;
        mx = max(sm2 - sm1,mx);
    }
    for (int i = 0;i <= n / 2 - sm1;i++)
        for (int j = 0;j <= n / 2 - sm2;j++)
            if (i - j >= mx)
                ans += 1ll * f[i][j] * f[n / 2 - sm2 - j][n / 2 - sm1 - i] % p,ans %= p;
    cout<<ans<<endl;
    return 0;
}