Spoj 4038. Counting The Way of Bracket Replacement Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MOD 100000

bool moduloUsed;
LL memo[200+10][200+10];
string s;

LL func(int left, int right)
{
    int i, valid;
    if(left>right)  return 1;

    if(memo[left][right]!=-1)   return memo[left][right];

    LL ret=0;

    for(i=left+1;i<=right;i+=2)
    {
        if(s[left]=='(' && s[i]==')') valid=1;
        else if(s[left]=='{' && s[i]=='}') valid=1;
        else if(s[left]=='[' && s[i]==']') valid=1;
        else if(s[left]=='?' && s[i]==')') valid=1;
        else if(s[left]=='?' && s[i]=='}') valid=1;
        else if(s[left]=='?' && s[i]==']') valid=1;
        else if(s[left]=='(' && s[i]=='?') valid=1;
        else if(s[left]=='{' && s[i]=='?') valid=1;
        else if(s[left]=='[' && s[i]=='?') valid=1;
        else if(s[left]=='?' && s[i]=='?') valid=3;
        else    valid=0;

        ret+=valid*func(left+1,i-1)*func(i+1,right);

        if(ret>MOD)
        {
            moduloUsed=true;
            ret%=MOD;
        }
    }
return memo[left][right]=ret;
}


int main()
{
    LL ans,length;

    while(cin>>length>>s)
    {
        SET(memo);
        ans=func(0,length-1);
        if(!moduloUsed)
        cout<<ans<<endl;
        else
        printf("%05lld\n",ans);
    }

return 0;
}