[A special feature on how to find "too much divided by 1000000007"! ~ From inverse element to discrete logarithm ~](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#5-%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0 -ncr) This is a Python version of the ** 5. Binomial coefficient nCr ** code in this document. (Thank you drken always)
MAX_NUM = 10**6 + 1
MOD = 10**9+7
fac = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv = [0 for _ in range(MAX_NUM)]
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
fac[i] = fac[i-1] * i % MOD
inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
finv[i] = finv[i-1] * inv[i] % MOD
def combinations(n,k):
if n < k:
return 0
if n < 0 or k < 0:
return 0
return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD