Catalan Numbers

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

const ll MOD = 1e9 + 7;

ll power(ll base, ll exp, ll mod) {
    ll res = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll modInv(ll x) { return power(x, MOD - 2, MOD); }

ll catalan(ll n) {
    ll res = 1;
    for (ll i = 0; i < n; i++)
        res = res % MOD * ((2 * n - i) % MOD) % MOD * modInv(i + 1) % MOD;
    return res % MOD * modInv(n + 1) % MOD;
}

const int MAXCAT = 5005;
ll cat_dp[MAXCAT];

void initCatalanDp(int n) {
    cat_dp[0] = cat_dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            cat_dp[i] = (cat_dp[i] + cat_dp[j] * cat_dp[i - j - 1]) % MOD;
}