If you implement it without thinking

nC_k = \frac{n!}{(n-k)!k!}

The definition of $ nC_k $ is ↑, so if you write this as it is in the code,

import math
def comb(n,k):
    math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

print(comb(4,2))
# 6

It looks like this. However, $ n! $ Is $ O (n) $, so in the case of $ n \ leqq10 ^ 9 $ like ABC156-D this time, the calculation time becomes long and it is not in time. I have to shorten the calculation time somehow.

Prerequisite knowledge

First you need to know the iterative squares method and Fermat's little theorem.

Repeated squares

How to find exponentiation at high speed. In python you can calculate the remainder of $ x ^ n $ divided by $ mod $ by using pow (x, n, mod).

Fermat's Little Theorem

When $ p $ is a prime number and $ a $ is an integer that is not a multiple of $ p $ ($ a $ and $ p $ are relatively prime), the following holds.

a^{p-1} \equiv 1 (mod\, p)

The point is that if you divide $ a ^ {p-1} $ by $ p $, it's too much.

Transform nCk

$ nC_k $ can be transformed as follows.

nC_k = \frac{n!}{(n-k)!k!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}

Now pay attention to $ \ frac {1} {k!} $.

From Fermat's Little Theorem

a^{p-1} mod\, p = 1 \\ \\
a^{p-2} mod\, p = \frac{1}{a} \\

You get $ a ^ {p-2} mod , p = \ frac {1} {a} $. Therefore, $ \ frac {1} {k!} = K! ^ {P-2} mod , p $ holds, and $ k! ^ {p-2} $ can be calculated at high speed by the iterative square method. , $ \ Frac {1} {k!} $ can be calculated at high speed.

From the above, $ nC_k $ can be expressed as follows.

nC_k = n(n-1)\cdots(n-k+1) \times(k!^{p-2}\,mod\,p)

The amount of calculation is $ O (k) . ( K! $ Takes the longest)

Implementation

# O(k)
def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

print(comb(4,2))
# 6

reference

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86 https://note.com/tanon_cp/n/ncff944647054

[Python] How to derive nCk (ABC156-D)