Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define p_b push_back
#define all(c) c.begin(), c.end()
#define mem(array, some_data) memset(array, some_data, sizeof array);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; //printf("%lld ", ll); to out put long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tree<int ,null_type,less<int >,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
const double eps = 1e-6;
const int MAXN = 2e5 + 3;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
bool ODD(ll O)
{
    return (O % 2 != 0);
}

ll lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}
int dx[] = {1, 0, -1, 0,-1, 1, -1, 1};
int dy[] = {0, 1, 0, -1,-1, 1, 1, -1};

bool is_power_of_2(int x) {
    if(x == 0) return true;
    return (ceil(log2(x)) == floor(log2(x)));
}
ll fast_power(ll a, ll b, ll mod) {
    ll ret = 1;
    while(b) {
        if(b & 1) {
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        b /= 2;
    }
    return ret;
}
/*------ never give up --------*/
ll ct_dp[502];
ll ans = 1;
ll x;
 ll catalan(ll n) {
    if(n <= 1) {
        return 1;
    }

    ll &ret = ct_dp[n];
    if(ret != -1) return ret;
    ret = 0;
    for(int i = 0; i < n; i++) {
        ret += catalan(i) % (MOD - 1) * catalan(n - i - 1) % (MOD - 1);
        ret %= (MOD - 1);
    }
    return ret;
 }
void solve(int test_case)
{
    mem(ct_dp , -1);
    ll n;
    cin >> n;
    if(ODD(n)) {
        cout << "0";
        return;
    }
    n -= 4;
    n /= 2;
    cout << fast_power(n , catalan(n), MOD);

}
int main()
{

    //ios_base::sync_with_stdio(0); cin.tie(0);
    int n = 1;
    //cin >> n;

    while (n--)
    {

        solve(n);
    }

    return 0;
}
Copy
Bracket Sequence OBITO
GNU G++17
3 ms
960 KB
Wrong Answer