Source Code
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;

inline int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
 
int n, dp[1001][1001][2];

int calc1(int idx, int cnt, bool put) {
    if (idx == n) return (cnt == 0 && put);
    if (cnt == 1000) return 0;
    
    int &ret = dp[idx][cnt][put];
    if (ret != -1) {
        return ret;
    }

    ret = 0;
    ret = add(ret, calc1(idx + 1, cnt + 1, put));
    if (cnt > 0) ret = add(ret, calc1(idx + 1, cnt - 1, put));
    if (!put && idx + 5 < n) ret = add(ret, calc1(idx + 5, cnt + 1, 1));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << calc1(0, 0, 0);
}
Copy
Bracket Sequence OsamaX01
GNU G++17
21 ms
8.9 MB
Wrong Answer