import sys
input = sys.stdin.readline
mod = 1000000007
N,K = map(int,input().split())
def cal(x,n):
if n == 1:
return x
cal2 = cal(x,n//2)
if n%2:
return cal2*cal2*x %mod
else:
return cal2*cal2 %mod
numer = denom = 1
for i in range(1,K+1):
numer = numer*(N+1-i) %mod
denom = denom*(i) %mod
denom = cal(denom,mod-2)
print(numer*denom%mod)
처음에는 "뭐야 너무 단순한 문제 아니야?" 라고 생각했었다. 그러면서도 당연히 무지성 곱셈하는 문제는 아니겠지? 했는데 역시 아니었다.
그냥 단순 곱셈, 나눗셈을 해서는 절대 풀 수 없는 문제였다. 왜 틀렸는지를 알아봤더니, 나머지를 계산한 후 나누기 계산을 하는것이 문제였다. 예를 들어서 만약 N이 1000000008, K가 2인 경우 정답은 500000004이다. 그러나 mod연산을 하고 나눗셈을 해주면 1/2가 되는 것이다.
어떻게 해결해야 하지 고민하던 중에 이전에 시그마 문제를 풀었던 기억이 났다. [백준 13172번] Σ (Python3) (tistory.com) 문제 읽을때 멀미났었던 문제였는데, 역시 쓰임새가 많으니 이런 문제를 냈었던 거구나 하는 생각이 들었다.
페르마의 소정리를 이용하면 쉽게 해결할 수 있다.
1. 분모와 분자를 따로 계산해주고, mod값으로 나눈 나머지를 구한다.
2. 나눗셈 연산을 페르마의 소정리를 이용해서 한다.
3. 결과 출력
오늘의 교훈) 페르마의 소정리를 잘 활용하자