파댕이의 케이크 만들기
시간 제한1초메모리 제한1024 MB
N가지 단이 각각 K개씩 있는 N×K개의 케이크 단을 임의 순서로 놓을 때, 아래 단이 아직 완성되지 않은 단이 나오지 않을 확률을 1e9+7로 나눈 나머지를 구한다.
문제
어릴 때부터 달달한 음식을 좋아했던 파댕이는 달달한 음식을 직접 만들고 싶어 했고, 식품 회사에서 인턴을 하게 되었다.

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

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