카드키 (Keycards)
시간 제한1초메모리 제한1024 MB
2N개의 가능한 열쇠 중 공집합이 아닌 부분집합을 골라, N개 위치 가운데 정확히 K개가 선택한 모든 열쇠에 구멍이 뚫려 있도록 하는 경우의 수를 1e9+7로 나눈 나머지로 구한다.
문제
JOI 봄 합숙이 열리는 시설의 숙박동 방 열쇠는 카드에 구멍이 여러 개 뚫린 모양이다. 구멍을 뚫을 위치의 후보는 N개 있고, 이 중 일부에 구멍을 뚫은 2N개의 서로 다른 열쇠가 만들어졌다.
당신은 JOI 봄 합숙을 위해 1개 이상 2N개 이하의 열쇠를 한꺼번에 받았다. 구멍을 뚫을 후보 위치를 맞추어 열쇠를 겹쳐 본 당신은, 정확히 K곳에서 받은 모든 열쇠에 구멍이 뚫려 있다는 것을 알아냈다.
이런 일이 일어나는 열쇠 조합은 몇 가지인가? 답을 1 000 000 007 (소수)로 나눈 나머지를 구하여라.
N과 K가 주어질 때, 답을 1 000 000 007로 나눈 나머지를 구하는 프로그램을 작성하여라.
입력
표준 입력에서 다음 입력을 읽는다.
- 1번째 줄에 정수 N, K가 공백을 구분으로 쓰여 있다.
출력
표준 출력에 열쇠 조합의 개수를 나타내는 1줄을 출력하여라. 출력의 1번째 줄에는 답을 1 000 000 007로 나눈 나머지를 써라.
제한
- 1 ≤ N ≤ 1 000 000 구멍을 뚫을 위치의 후보 개수
- 0 ≤ K ≤ N 받은 모든 열쇠에 구멍이 뚫려 있는 위치의 개수