记录编号	572266	评测结果	AAAAAAAAAA
题目名称	[CF629C]Famil Door and Brackets	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.231 s
提交时间	2022-06-29 16:39:55	内存使用	25.55 MiB

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int maxm = 2e3 + 5;
char s[maxn];
int n, m, cnt;
long long f[maxm][maxm];
int main() {
	freopen("tribrackets.in", "r", stdin);
    freopen("tribrackets.out", "w", stdout);
	cin >> n >> m;
	scanf("%s", s + 1);
	f[0][0] = 1;
	for(int i = 1; i <= n - m; i ++) {
		f[i][0] = f[i - 1][1]; 
		for(int j = 1; j <= i; j ++) {
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j + 1]) % mod;
		}
	}
	int cur = 0;
	cnt = 1e9;
	for(int i = 1; i <= m; i ++) {
		if(s[i] == '(') {
			cur ++;
		}
		else {
			cur --;
		}
		cnt = min(cnt , cur);
	}
	long long ans = 0;
	for(int i = 0; i <= n - m; i ++) {
		for(int j = max(-cnt, 0); j <= i && j + cur <= n - m - i; j ++) {
			ans += ((f[i][j] * f[n - m - i][j + cur]) % mod) % mod;
			ans %= mod;
		}
	}
	cout << ans << endl;
	return 0;
}