Python で mod. p での二項係数 (nCk mod. p) の求め方

過去記事, Python で mod の下での逆元を計算するテーブルを作成する - わかばめにっき では, modの下での階乗の逆元を求めました.

本記事では, 以下の記事を参考にして二項係数 を前処理 , 実行 で行うアルゴリズムを紹介します.
drken1215.hatenablog.com

MAX = 10**7 # n の取りうる最大値( ただし, Pより小さいものとする )を取る

P = 10**9 + 7 # P は十分大きく、かつ素数である
fac = [1] + [1]
finv = [1] + [1]
inv = [0] + [1]

for i in range(2, MAX):
    fac += [fac[-1] * i % P]
    inv += [P - inv[P%i] * (P // i) %P]
    finv += [finv[-1] * inv[i] % P]


def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * finv[k] * finv[n-k] % P

例えば, ABC 021 D - 多重ループをACすることができます
atcoder.jp