Lucas's theorem - YessineJallouli/Competitive-Programming GitHub Wiki

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

const int N =  1e6 + 100;
const int mod = 2e6+3 ;
vector<ll> Fact,Invfact,Inv;

void compute() {
    Fact.resize(mod);
    Invfact.resize(mod);
    Inv.resize(mod);
    Fact[0] = Fact[1] = 1;
    Invfact[0] = Invfact[1] = 1;
    Inv[0] = 1;
    Inv[1] = 1;
    for (int i = 2; i < mod; i++) {
        Fact[i] = (Fact[i - 1] * i) % mod;
        Inv[i] = ((mod - mod / i) * Inv[mod % i]) % mod;
        Invfact[i] = (Invfact[i - 1] * Inv[i]) % mod;
    }
}

ll nCk(ll N,ll R,ll P) {
    if (R < 0 || R > N)
        return 0;
    if (R == 0 || R == N)
        return 1;
    if (N >= P)
        return (nCk(N / P, R / P, P) * nCk(N % P, R % P, P)) % P;
    return (Fact[N] * (Invfact[N - R] * Invfact[R]) % P) % P;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    compute();
}