Source Code
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define answer(x) cout << (x ? "YES\n" : "NO\n")
#define test ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--)
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
using namespace std;

const int  N = 1010, mod = 1e9 + 7, M = 1 << 4;
int n, dp[N][N][M][2]; 


ll solve(int i, int opened, int mask, int gotIt)
{
	if(i > n) return (!opened && gotIt); 
	 
	int &ret = dp[i][opened][mask][gotIt]; 
	if(ret + 1) return ret; 
	ret = 0; 
	
	if((mask & (1 << 4)) != 0) mask -= 16; 
	mask <<= 1;


	// try to open 
	ret = ret + (solve(i + 1, opened + 1, mask + 1, gotIt) % mod); 
	ret %= mod;
	
	// try to close
	if(opened)
	{		
		ret = ret + (solve(i + 1, opened - 1, mask, gotIt || mask == 28) % mod), 
		ret %= mod; 
	}
	
	return ret; 
}


int main()
{	
	go; 
	memset(dp, -1, sizeof dp); 
	cin >>n; 
	cout << solve(1, 0, 0, 0); 
}



Copy
Bracket Sequence MuhammedAlajam
GNU G++17
411 ms
129.0 MB
Accepted