Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int n;
const ll M = 1000000007;
ll fact[1010];


ll add(ll a, ll b){
	return ((ll)(a%M)+(b%M)+M)%M;
}
ll mult(ll a, ll b){
	return add((a%M)*(b%M),0);
	// return ((((a%M)*(b%M))%M); 
}
ll pow(ll a, ll b){
	ll r = 1;
	if(b == 1)
		return a;
	r = pow(a,b/2);
	r = mult(r,r);
	if(b%2 == 1)
		r = mult(r,a);
	return r;
}

void precomp(){
	fact[0] =1;
	for(int i=1;i<1010; ++i){
		fact[i] = mult(i,fact[i-1]);
	}
}

ll get(ll n){
// return the number of bracket sequences of size N
	// C(N,N/2)/((N/2)+1)
	ll ret = mult(fact[n],pow(fact[n/2],M-2));
	ret = mult(ret, pow(fact[n/2],M-2));
	ret = mult(ret, pow( (n/2)+1,M-2));
	
	// ret = mult(fact[n],pow(mult(fact[n/2],fact[n/2]),M-2));
	// ret = mult(ret, pow( (n/2)+1,M-2));
	return ret;
}

int main(){
    cin>>n;
    precomp();
    if(n%2==1 || n<6){
    	cout<<0<<endl;
    	return 0;
    }
    
    int ans = 1;
    int k = n-4;
    
    // cout<<"get(6) = "<<mult(fact[6],pow(fact[3],M-2))<<endl;
    
    
    ans = mult( get(k), (k/2));
	cout<<ans;
	
    return 0;
}
Copy
Bracket Sequence Saq
GNU G++17
3 ms
860 KB
Wrong Answer