Source Code
#include <iostream>
#include <vector>

using namespace std;

long long mod = 1e9+7;

vector<vector<long long>> v(1001, vector<long long>(501, -1));
long long solve(int n, int l = 0){
    if( n < l )
        return 0;
    if(n == l)
        return 1;
    
    if(v[n][l] != -1)
        return v[n][l];

    if( l == 0 )
        return solve(n-1, 1);
    
    v[n][l] = (solve(n-1, l-1) + solve(n-1, l+1))%mod;
    return v[n][l];
}

int main(){
    int n; cin >> n;

    if(n < 6 || n%2 == 1){
        cout << 0 << endl;
        return 0;
    }

    int ans = solve(n-4)*(n/2-2);

    cout << ans << endl;

    return 0;
}
Copy
Bracket Sequence Trainee
GNU G++17
9 ms
4.9 MB
Wrong Answer