시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 21 6 6 28.571%

문제

공대 2학년이 되는 태영이는 올해 들어올 신입생들을 위한 MT를 준비하고 있다.

다른 준비는 다 끝났고, MT의 꽃이라 할 수 있는 '랜덤 게임'만 준비하면 된다.

태영이는 올해 N명의 신입생들이 입학한다는 것은 알지만, 이들 중 남자와 여자가 몇 명인지는 모른다.

태영이는 게임을 진행하기 위해서, 이 N명의 학생들을 원탁에 둘러 앉힐 계획이다.

여학생이 상대적으로 적은 공대에서 1년을 보낸 태영이는 남자들이 연속해서 앉는 것을 안타깝게 생각한다.

그래서 태영이는 "K명보다 많은 남자들이 연속해서 앉을 수 없다"라는 규칙을 만들었다.

태영이의 규칙을 만족하도록 N명의 신입생들을 원탁에 앉히는 경우의 수를 구해보자.

단, 태영이는 N명 중 남자가 몇 명인지 모르기 때문에 남학생 수는 0명부터 N명까지 모두 가능하다.

또한, 신입생들은 원탁에 둘러 앉을 것이므로 회전해서 같은 배치는 동일한 배치로 취급한다.

예를 들어, 남자를 M, 여자를 W라 했을 때,  MMWW와 WWMM, WMMW는 모두 같은 배치다.

입력

첫째 줄에 NK가 사이에 공백을 두고 순서대로 주어진다. (1 ≤ N, K ≤ 3000)

KN보다 클 수 있음에 유의하라.

출력

태영이의 규칙을 만족하는 모든 배치 방법의 수를 출력한다. 답이 매우 커질 수 있으므로, 108+7로 나눈 나머지를 출력한다.

예제 입력 1

4 2

예제 출력 1

4

MMWW, MWMW, MWWW, WWWW로 총 4가지가 가능하다.

예제 입력 2

3 2

예제 출력 2

3