Backdrop

백준 온라인 저지 ▸ 11401

이항 계수 3
I

문제

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 4,000,000, 0 ≤ \(K\) ≤ \(N\))

출력

\(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

풀이

python

코드

p = 1_000_000_007
 
 
def perm(n, k):
    mul = 1
    for i in range(n, n - k, -1):
        mul = mul * i % p
 
    return mul
 
 
def pow(n, k):
    if k == 1:
        return n % p
 
    if k % 2 == 0:
        return pow(n**2 % p, k // 2)
    else:
        return pow(n**2 % p, k // 2) * n % p
 
 
def comb(n, k):
    return perm(n, k) * pow(perm(k, k), p - 2) % p
 
 
n, k = map(int, input().split())
 
print(comb(n, k))