[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 11401번 _ 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

[아이디어]

1) 일반적인 접근으로는 시간초과가 난다.

2) mod만 구하면 된다는 것에 착안하여 페르마 소정리를 활용, 각 분모 분자에 대한 mod만 구한다.

3) pow() 함수를 이용해 modulo 역을 쉽게 구할 수 있다.

 

m,n=map(int,input().split())
mod = 1000000007
a=1;b=1
for i in range(n):
    a*=m-i
    a%=mod
for i in range(1,n+1):
    b*=i
    b%=mod
b = pow(b,-1,mod)
print((a*b)%mod)