You can calculate N! in O(log(N)) using Matrix Multiplication, then calculate N! / [ K! * (N — K)! ] % mod How ? (only when mod is prime)

(A / B) % mod = A * Pow(B, mod — 2) % mod

Another approach is precalculate 10⁶!, (2·10⁶)!, ..., 10⁹! locally and paste it in your code. Then you can easily calculate every factorial using 10⁶ multiplications.

Way 1: Precalculate the factorials. Then, use Fermat's Little theorem, which says that says that $$$a^{-1} \equiv a^{p - 2} \pmod{p}$$$. This allows us to sort of transform modular division into modulo multiplication and then some powers. The pre-computing factorial is $$$O(n)$$$, dealing with the denominator is $$$O(\log(N))$$$ if you use fast exponentiation.

Way 2: Pascal's Identity. Straight forward dynamic programming. This is $$$O(n^2)$$$.

Optimization: Use Lucas's theorem.

You can calculate C(n,k) = n! * reverse((n — k)!) * reverse(k!) which reverse(a) = power(a, mod — 2)

If you have enough memory, you can save first a! into an array