DIU Team Selection Contest 2 G

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define inf 0x3f3f3f3f
const ll mod = 1e9+7;

ll n;
string s;

ll f(int ind, string p, ll sum){
    if(sum<0) return 0;
    if(ind == n){
        cout<<p<<endl;
        stack<int> st;
        bool valid = true;
        for(ll i = 0; i<n; i++){
            if(st.empty()){
                if(p[i]==')'){
                    valid = false;
                    break;
                }
                else{
                    st.push(p[i]);
                }
            }
            else{
                if(p[i]=='('){
                    st.push(p[i]);
                }
                else if(p[i]==')'){
                    if(st.top()=='('){
                        st.pop();
                    }
                    else{
                        valid = false;
                        break;
                    }
                }
            }
        }
        if(valid && st.empty()) return 1;
        return 0;
    }
    if(s[ind]=='?'){
        ll x = f(ind+1, p, sum-1);
        ll y = f(ind+1, p, sum+1);
        return (x+y)%mod;
    }
    if(s[ind]=='('){
        
    }
    return f(ind+1, p)%mod;

}
void solution(){
    cin>>n>>s;
    string p = "";
    ll ans = f(0, p, 0)%mod;
    cout<<ans<<endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll tcase = 1;
    //cin>>tcase;
    for(ll tc = 1; tc<=tcase; tc++){
        //cout<<"Case "<<tc<<": ";
        solution();
    }
}