50pts玄关求助

#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
string s;
int xx[100005];
int ad[100005], mi[100005]; 
void prepp(int n) {
    int lstp = -1, lstm = -1;
    int x = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') x++;
        else if (s[i] == ')') x--;
        
        ad[i] = (x == 0 && s[i] == '+') ? i : lstp;
        mi[i] = (x == 0 && s[i] == '*') ? i : lstm;
        if (x == 0) {
            if (s[i] == '+') lstp = i;
            else if (s[i] == '*') lstm = i;
        }
    }
}
int gtr(int ll, int rr, int exp) {
    int len = rr - ll + 1;
    if (len == 0) return 1;
    if (len == 1) {
        if (s[ll] == '+') return exp == 1 ? 3 : 1;
        else if (s[ll] == '*') return exp == 1 ? 1 : 3;
    }
    int lstad = -1, lstmi = -1;
    if (xx[rr] == xx[ll]) {
        lstad = ad[rr];
        lstmi = mi[rr];
        while (lstad >= ll && (s[lstad] != '+' || xx[lstad] != xx[ll])) lstad--;
        while (lstmi >= ll && (s[lstmi] != '*' || xx[lstmi] != xx[ll])) lstmi--;
    }
    if (lstad != -1 && lstad >= ll) {
        if (exp == 1) {
            return (gtr(ll, lstad - 1, 1) * gtr(lstad + 1, rr, 0) % mod + 
                    gtr(ll, lstad - 1, 1) * gtr(lstad + 1, rr, 1) % mod + 
                    gtr(ll, lstad - 1, 0) * gtr(lstad + 1, rr, 1) % mod) % mod;
        } else {
            return gtr(ll, lstad - 1, 0) * gtr(lstad + 1, rr, 0) % mod;
        }
    }
    else if (lstmi != -1 && lstmi >= ll) {
        if (exp == 1) {
            return gtr(ll, lstmi - 1, 1) * gtr(lstmi + 1, rr, 1) % mod;
        } else {
            return (gtr(ll, lstmi - 1, 1) * gtr(lstmi + 1, rr, 0) % mod + 
                    gtr(ll, lstmi - 1, 0) * gtr(lstmi + 1, rr, 0) % mod + 
                    gtr(ll, lstmi - 1, 0) * gtr(lstmi + 1, rr, 1) % mod) % mod;
        }
    }
    else {
        return gtr(ll + 1, rr - 1, exp);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int l;
    cin >> l >> s;
    int cnt = 0;
    for (int i = 0; i < l; i++) {
        if (s[i] == '(') cnt++;
        else if (s[i] == ')') cnt--;
        xx[i] = cnt;
    }
    prepp(l);
    cout << gtr(0, l - 1, 0);
    return 0;
}