파댕이의 케이크 만들기
시간 제한1초메모리 제한1024 MB
N종류의 층이 각각 K개씩 무작위 순서로 주어질 때, 모든 층을 쌓을 수 있는 확률을 10^9+7로 나눈 값으로 구합니다.
문제
어릴 때부터 달달한 음식을 좋아했던 파댕이는 달달한 음식을 직접 만들고 싶어 했고, 식품 회사에서 인턴을 하게 되었다.

파댕이가 맡은 첫 번째 일은 개의 케이크 단을 쌓는 것이다. 파댕이는 매일 개의 케이크를 쌓아 완성해야 하며, 케이크는 가장 아랫단부터 가장 윗단까지 순서대로 쌓아야 한다. 1번째 단은 바로 쌓을 수 있다. 1 이상의 정수 에 대해, 번째 단은 1번째부터 번째 단까지만 올라가 있는 케이크 위에만 올릴 수 있다.

매일 출근해 케이크를 만들던 파댕이는 작업 중에 올릴 수 없는 케이크 단을 받을 확률이 상당히 높다는 것을 깨달았다. 작업 중간에 올릴 수 없는 단을 받는 것이 작업 능률에 심각한 문제라고 생각한 파댕이는 문제를 제기하려고 "임의의 순서로 케이크 단이 주어질 때, 작업 중간에 올릴 수 없는 케이크 단이 주어지지 않을 확률"을 계산해 보고하기로 했다. 파댕이를 대신해 확률을 계산해 주자!
입력
첫째 줄에 케이크의 단 수 과 만들어야 하는 케이크 수 가 공백으로 구분되어 주어진다. (, )
출력
개의 케이크 단이 임의의 순서로 주어질 때, 중간에 올릴 수 없는 케이크 단이 주어지지 않을 확률을 라고 하자. 이때 을 출력한다. 은 의 모듈러 곱셈에 대한 역원이고, 와 는 서로소이다. 주어진 제약 조건에서 의 값이 유일하게 존재함을 증명할 수 있다.
이다.
힌트
개의 케이크 단에는 개의 단이 개씩 포함되어 있다.