Combinari

int invers(int x) {
    int exp = mod - 2, ans = 1;
    while(exp) {
        if(exp & 1)
            ans = (ans * x) % mod;
        x = (x * x) % mod;
        exp >>= 1;
    }
    return ans;
}

int comb(int n, int k, vector < int >& fact) {
    int ans = fact[n];
    ans = (ans * invers(fact[k])) % mod;
    ans = (ans * invers(fact[n - k])) % mod;
    return ans;
}