Binomial Coefficient

$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{(n-m)!m!}=\frac{n(n-1)\cdots (n-k-1)}{1\cdot 2\cdot 3\cdots k}$

Implementation stolen from: https://cp-algorithms.com/combinatorics/binomial-coefficients.html#improved-implementation

int C(int n, int k) {
    double res = 1;
    for (int i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (int)(res + 0.01)

A simple recursive implementation

ll choose(n, k) {
 
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k
}

Another Note: $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-m}\right)$

Recently, I tried to use this formula for this Codeforces problem https://codeforces.com/contest/1999/submission/277997377, but I ran into integer overflow problems, even after using long long.

They do something like this in the solution https://codeforces.com/blog/entry/132373 (Problem F) This is the tourist solution https://codeforces.com/contest/1999/submission/274741514

Yes, actually, CP algorithms teaches how to tackle this.

Factorial module $\%$ MOD

The modular inverse here

int inv(int a) {
  return a <= 1 ? a : MOD - (long long)(MOD/a) * inv(MOD % a) % MOD;
}

• https://cp-algorithms.com/algebra/module-inverse.html#mod-inv-all-num

factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1] * i % MOD;
}

ll C(ll n, ll k) {
    return factorial[n] * inv(factorial[k] * factorial[n - k] % MOD) % MOD;
}