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 <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
char character[] = {'(', ')'};
int mod = 1e9 + 7;
pair<int, int> process(const string& str, int flag) {
    int len = str.size();
    vector<int> d;
    vector<vector<long long>> dp(len + 1, vector<long long>(len + 1, 0));
    vector<vector<long long>> presum(len + 1, vector<long long>(len + 1, 0));
    for (int i = 0; i < len; i++) {
        if (str[i] == character[flag]) {
            d.push_back(i);
        } else if (!d.empty()) {
            d.pop_back();
        }
    }
    if (d.empty()) {
        return {0, 1};
    }
    int preindex = d[0];
    int top = 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX