Combinatorics: nCr, Pascal's Triangle, and Catalan Numbers

MOD = 10**9 + 7

# Approach 1: Pascal's triangle
def pascal(n):
    C = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        C[i][0] = 1
        for j in range(1, i + 1):
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
    return C

# Approach 2: Precomputed factorials
def build_comb(max_n, mod=MOD):
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], mod - 2, mod)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % mod
    def C(n, k):
        if k < 0 or k > n: return 0
        return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod
    return C

C = build_comb(10**6)
print(C(10, 3))   # 120
print(C(20, 10))  # 184756

# Catalan numbers: C(2n, n) / (n+1)
def catalan(n, C_func):
    return C_func(2*n, n) * pow(n+1, MOD-2, MOD) % MOD

# Catalan(n) counts:
# - Balanced parentheses of length 2n
# - Binary search trees with n nodes
# - Triangulations of (n+2)-gon
# - Non-crossing partitions
for i in range(8):
    print(f"Catalan({i}) = {catalan(i, C)}")
# 1, 1, 2, 5, 14, 42, 132, 429

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

const long long MOD = 1e9 + 7;

long long power(long long b, long long e, long long m = MOD) {
    long long r = 1; b %= m;
    while (e > 0) { if (e&1) r=r*b%m; b=b*b%m; e>>=1; }
    return r;
}

struct Comb {
    vector<long long> fact, inv_fact;
    Comb(int n) : fact(n+1), inv_fact(n+1) {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1]*i%MOD;
        inv_fact[n] = power(fact[n], MOD-2);
        for (int i = n-1; i >= 0; i--) inv_fact[i] = inv_fact[i+1]*(i+1)%MOD;
    }
    long long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;
    }
    long long catalan(int n) {
        return C(2*n, n) * power(n+1, MOD-2) % MOD;
    }
};

public class Combinatorics {
    static final long MOD = 1_000_000_007L;
    long[] fact, invFact;

    public Combinatorics(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n-1; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
    }

    long power(long b, long e) {
        long r = 1; b %= MOD;
        while (e > 0) { if ((e&1)==1) r=r*b%MOD; b=b*b%MOD; e>>=1; }
        return r;
    }

    long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
    }
}