[Python] 백준 11401 이항 계수 3

백준 11401 이항 계수 3
문제

자연수 N과 정수 K가 주어졌을 때 이항 계수

를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

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

출력

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

---

제출

n,k=map(int,input().split())
p=1000000007
def d(a,b):
    if b==0:
        return 1
    if b%2:
        return (d(a,b//2)**2*a)%p
    else:
        return (d(a,b//2)**2)%p
f=[1 for _ in range(n+1)]
for i in range(2,n+1):
    f[i]=f[i-1]*i%p
print((f[n]%p)*(d(((f[n-k]*f[k])%p),p-2)%p)%p)

예제

5 2

결과

백준 11401 이항 계수 3

 

11401번: 이항 계수 3