Binomial Modulo Small Prime — Solution & Editorial

Back to the Problem

Lucas' theorem: C(N, K) mod P = ∏ C(N_i, K_i) mod P over the base-P digits of N and K. Each small binomial uses factorials mod P.

Complexity: O(log_P N · P)

Watch out: A digit of K exceeding the corresponding digit of N makes the whole product 0 — the core of Lucas.