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;
int dp[1001][1001][2][2][2][2][2];
int n;
int solve(int idx, int cnt, int a, int b, int c, int d, 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][d][k];
	if (tmp != -1)
		return tmp;
	tmp = 0;
	int p = k;
	if (a == 0 and b == 0 and c==0 and d == 1){
		tmp += solve(idx+1,cnt+1,b,c,d,0,p)%MOD;
		tmp %= MOD;
		if (cnt > 0){
			tmp += solve(idx+1,cnt-1,b,c,d,1,1)%MOD;
		tmp %= MOD;
		}
	} else {
		tmp += solve(idx+1,cnt+1,b,c,d,0,p)%MOD;
		tmp %= MOD;
		if (cnt > 0){
			tmp += solve(idx+1,cnt-1,b,c,d,1,p)%MOD;
		tmp %= MOD;
		}		
	}

	return tmp%MOD;

}
signed main() {

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

	cin >> n;
	if (n &1 or n <= 5) {
		cout << 0 << endl;
		return 0;
	}
	memset(dp,-1,sizeof(dp));
	cout << solve(0,0,1,1,1,1,0);


	/*
	
	


	*/


}
Copy
Bracket Sequence MysteRrion
GNU G++17
429 ms
252.1 MB
Accepted