[백준/BOJ] gold1 - 11041번 이항 계수 3 (Python)

▶11401 - 이항 계수 3

▶문제

자연수 n과 정수 k가 주어졌을 때 이항 계수 nCk를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 4,000,000, 0 ≤ k ≤ n)

 

▶출력

nCk를 1,000,000,007로 나눈 나머지를 출력한다.

 

▶풀이

 

#페르마의 소정리
#(a/b)%p
# = (a * b^-1) % p
# = (a * b^-1 * b^(p-1)) % p
# = (a * b^(p-2)) % p
# = (a % p) * (b^(p-2) % p) % p

def pow(a,b):
    if b == 0:
        return 1
    if b % 2 == 1:
        return (pow(a, b//2)**2*a)%p
    else:
        return (pow(a, b//2)**2)%p


n, k = map(int, input().split())
p = 1000000007
factorial = [1 for i in range(n+1)]

for i in range(2, n+1):
    factorial[i] = factorial[i-1]*i % p

A = factorial[n]
B = (factorial[n-k]*factorial[k])%p

print((A%p) * (pow(B, p-2) % p) %p)