1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 1;
using ll = long long;
int N, M, K;
string str;
int f[2002][2002];
int limit[2002];
int pre_sum[2][2002];
pair<int, int> Handle(string& s) {
    memset(f, 0, sizeof(f));
    memset(limit, 0, sizeof(limit));
    memset(pre_sum, 0, sizeof(pre_sum));
    int cur = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            cur++;
        } else {
            cur--;
        }
    }
    if (cur == 0) {
        return make_pair(0, 1);
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX