Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define PI acos(-1)
#define fr first
#define se second
#define int long long
const int MAXN = 1001;
const int MOD = 1e9 + 7;
typedef tree<int , null_type ,  less<int> , rb_tree_tag ,
	tree_order_statistics_node_update> os;


int dp[1001][1001][3][3][3][2];
int n;
int solve(int idx, int cnt, int a, int b, int c, int k){
	if (idx > n) 
		return 0;
	if (idx == n){
		if (cnt == 0){
			return k;
		}
		return 0;
	}
	int &tmp = dp[idx][cnt][a][b][c][k];
	if (tmp != -1){
		return tmp;
	} 
	tmp = 0;
	
	if (a == 1 and b == 1 and c == 1 and k == 0){
		tmp += solve(idx+2,cnt+2,c,1,1,k)%MOD;
		tmp%= MOD;
		if (cnt > 1)
			tmp += solve(idx+2,cnt-2,c,2,2,1)%MOD;
		tmp %= MOD;
		tmp += solve(idx+2,cnt,c,1,2,k)%MOD;
		tmp %= MOD;
		if(cnt > 0)
			tmp += solve(idx+2,cnt,c,2,1,k)%MOD;
		tmp %= MOD;
		tmp += solve(idx+1,cnt+1,b,c,1,k)%MOD;
		tmp %= MOD;
	} else {
		tmp += solve(idx+1,cnt+1,b,c,1,k)%MOD;
		tmp %= MOD;
		if (cnt > 0){
			tmp += solve(idx+1,cnt-1,b,c,2,k)%MOD;
		tmp %= MOD;
		}
	}

	return tmp;

}
signed main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	memset(dp,-1,sizeof(dp));
	cout << solve(0,0,0,0,0,0)%MOD;


	/*
	
	


	*/


}
Copy
Bracket Sequence MysteRrion
GNU G++17
171 ms
262.1 MB
Memory Limit Exceeded