#2015 탈출한 소들

22  5 s   128 MB  

Description

농부 동이는 N마리의 소를 키우며, 각 소마다 0번 부터 N-1번의 번호를 붙였다.

어느날 동이는 K마리의 소가 탈출했다는 사실을 알았다. 당시 동이는 볼일을 보러 시내에 나가있던 상황이고, 근처에 지나가던 한 여우가 탈출한 소들의 번호의 합을 헤아렸고 여우는 동이에게 합이 N으로 나눠지는 숫자다 라는것을 전화를 통해 제보하였다.

농장으로 돌아가던 차에 동이는 과연 어떤 소들이 탈출을 했을지가 궁금해졌고, 친구이자 유능한 프로그래머인것 같이 보이는 당신에게 전화를 하였고 다음과 같은 문제를 생각해냈다. N과 K가 주어질 때, 가능한 탈출한 소들의 조합이 총 몇가지인지 구하는 프로그램을 작성하라. 숫자가 매우 클 수 있기 때문에 1,000,000,007로 나눈 나머지를 출력해야한다.

Input

입력은 1이상 1,000이하의 정수 N과 1이상 47이하의 정수 K가 주어진다.

Output

탈출한 소들의 조합의 총 가짓수를 1,000,000,007로 나눈 나머지를 출력한다.

Sample Input

Sample Output

7 4
5

Sample Input 2

58 4

Sample Output 2

7322

Hint

 

첫 예시의 경우에 가능한 조합은 (0,1,2,4), (0,3,5,6), (1,2,5,6), (1,3,4,6), (2,3,4,5) 총 5가지가 존재한다.