Source Code
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned ll
constexpr auto PI = 3.141592653589793238462643383279502884;

const ll  MM = 1e9 + 7, N = 2e3 + 10;
const ll MAX = 2e18;
using namespace std;

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
ll numberOfDiviser(ll a) {
	if (a == 1)return 0;
	ll ans = 1;
	ll i;
	for (i = 2; i * i < a; i++) {
		if (a % i == 0)ans += 2;
	}
	if (i * i == a)ans++;
	return ans;
}

ll pow(ll a, ll b, ll m) {
	if (b == 0)return 1;
	if (b == 1)return a;
	ll x = pow(a, b / 2, m);
	x = (x * x) % m;
	if (b % 2)x = (x * a);
	return x % m;
}
ll inverse_mod(ll a, ll m) {
	return pow(a, m - 2, m);
}
int n;
ll dp[N][N][8];

ll DP(int i=0, int j=0, int last=0) {
	if (i == n)return (j==0&&last==5);
	if (dp[i][j][last] + 1)return dp[i][j][last];
	ll res = 0;
	int last1;
	if (last < 3)last1 = last + 1;
	else if (last == 3 || last == 5)last1 = last;
	else last1 = 0;
	res += DP(i + 1, j + 1, last1);

	if (last < 3)last1 = 0;
	else if (last < 5)last1 = last + 1;
	else last1 = 5;
	if(j)
		res += DP(i + 1, j - 1, last1);
	return dp[i][j][last] = res%MM;
}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	std::cout.tie(0);
	int t = 1;//cin >> t;
	int i = 1;
	while (t--) {
		//cout << "Case #" << i++ << ": ";
		solve();
	}
}
/*

*/
Copy
Bracket Sequence srdamaa7
GNU G++17
201 ms
254.1 MB
Wrong Answer