올바른 괄호 문자열

#include <bits/stdc++.h>

#define MAX_N 201
#define ll long long
using namespace std;

ll n, mod = 1e5;
string s;
ll dp[MAX_N][MAX_N];

unordered_map<char, char> mp {{'[',']'},{'{','}'},{'(',')'}};

ll solve(ll l, ll r) {
    if(l > r) return 1;
    ll& res = dp[l][r];
    if(res != -1) return res;
    res = 0;

    for(ll i = l + 1; i <= r; i += 2) {
        for(auto& [op, co] : mp) {
            if((s[l] == op or s[l] == '?') and (s[i] == co or s[i] == '?')) {
                res += solve(l + 1, i - 1) * solve(i + 1, r);
                if(res >= mod) res = mod + res % mod;
            }
        }
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof(dp));
    cin >> n >> s;
    auto res = (n & 1 ? 0 : solve(0, n - 1));
    if(res >= mod) printf("%05lld",res%mod);
    else cout<<res;
    return 0;
}