Source Code
#include<iostream>
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int mod=1e9+7;
const ll INF=1e18;
const double pi=3.14159265358979323846;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define Go ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;

int sum(int x,int y){
    if((x+=y)>=mod)
        x-=mod;
    return x;
}

int n;
int dp[1010][1010][11];

int solve(int i,int b,int f)
{
    if(i==n){
        if(b==0&&f==5)return 1;
        else return 0;
    }
    if(dp[i][b][f]!=-1)return dp[i][b][f];

    int c1=0,c2=0;

    if(f<3){
        c1=solve(i+1,b+1,f+1);
        if(b>0)c2=solve(i+1,b-1,0);
    }
    else if(f==5){
        c1=solve(i+1,b+1,f);
        if(b>0)c2=solve(i+1,b-1,f);
    }
    else if(f==3){
        c1=solve(i+1,b+1,f);
        if(b>0)c2=solve(i+1,b-1,f+1);
    }
    else if(f==4){
        c1=solve(i+1,b+1,1);
        if(b>0)c2=solve(i+1,b-1,f+1);
    }

    return dp[i][b][f]=sum(c1,c2);
}

int main()
{
Go

memset(dp,-1,sizeof(dp));

cin >> n;

int ans=solve(0,0,0);

cout << ans;

return 0;
}
Copy
Bracket Sequence yumna08
GNU G++17
70 ms
45.1 MB
Accepted