bin power + combinations + factorial + inv

struct combinatorics {
    vector<int> fact, inv, two;
    int n;

    int bp(int num, int pow) {
        int res = 1;
        while (pow) {
            if (pow & 1) res = num * res % M;
            pow >>= 1;
            num = num * num % M;
        }
        return res;
    }

    combinatorics(int nn) {
        int n = nn + 10;
        fact.assign(n, 0);
        inv.assign(n, 0);
        two.assign(n, 0);

        two[0] = 1;
        for (int i = 1; i < n; i++) two[i] = two[i - 1] * 2 % M;
        fact[0] = 1;
        for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % M;
        inv[n - 1] = bp(fact[n - 1], M - 2);
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % M;
    }

    int comb(int n, int k) {
        return fact[n] * inv[n - k] % M * inv[k] % M;
    }

    int cat(int n) {
        return fact[2 * n] * inv[n] % M * inv[n + 1] % M;
    }
};
combinatorics cc(1e6);