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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second

const long double PI = atan(1) * 4.0;

const int N = 1001;
const int M = 5;
const int MOD = 1000000007;

int dp[N][N][(1 << M)][2];
int n;
int calc(int ind, int cnt, int mask, bool found){
    int prev_found = found;
    if(mask == 7){
        found = 1;
    }
    if(ind == n){
        return found && cnt == 0;
    }
    if(cnt < 0){
        return 0;
    }
    if(dp[ind][cnt][mask][prev_found] != -1){
        return dp[ind][cnt][mask][prev_found];
    }
    int new_mask = 0;
    for(int i = 1; i < 5; i++){
        if((1 << i)&mask){
            new_mask |= (1 << (i - 1));
        }
    }
    return dp[ind][cnt][mask][prev_found] = (calc(ind + 1, cnt + 1, (new_mask | (1 << 4)), found) + calc(ind + 1, cnt - 1, new_mask, found))%MOD;
}
int main(){
    FAST
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << calc(0, 0, 0, 0) << endl;
    /*int ans = 0;
    for(int i = 0; i < (1 << n); i++){
        bool ok = 1;
        int cnt = 0;
        string s = "";
        for(int j = 0; j < n; j++){
            if((1 << j)&i){
                cnt++;
                s += '(';
            }
            else{
                cnt--;
                s += ')';
            }
            if(cnt < 0){
                ok = 0;
            }
        }
        ok &= cnt == 0;
        bool two = 0;
        for(int j = 0; j + 5 < n; j++){
            string ss = "";
            for(int k = j; k < j + 5; k++){
                ss += s[k];
            }
            if(ss == "((())"){
                two = 1;
            }
        }
        if(two && ok){
            ans++;
        }
    }
    cout << ans << endl;*/
    return 0;
}
Copy
Bracket Sequence Basilhijaz
GNU G++17
652 ms
252.0 MB
Accepted