시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 123 44 27 27.551%

문제

수빈이는 BOJ 알고리즘 캠프에서 음악을 들으면서 문제를 풀고 있다. 지금 수빈이의 스마트폰에는 N개의 노래가 저장되어 있다. 오늘 수빈이는 P개의 노래를 들으려고 한다. 수빈이는 다음과 같은 조건을 만족하는 플레이리스트를 만드려고 한다. 플레이리스트에는 같은 노래가 여러 번 들어 있어도 된다.

  • 모든 노래는 적어도 한 번씩 들어야 한다.
  • 같은 노래를 들으려면, 플레이리스트에서 두 노래 사이에 적어도 M개의 곡이 있어야 한다.

수빈이는 플레이리스트를 만들 수 있는 경우의 수가 궁금해졌다. N, M, P가 주어졌을 때, 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, P가 주어진다. (1 ≤ N ≤ 100, 0 ≤ M ≤ N, N ≤ P ≤ 100)

출력

첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

1 0 3

예제 출력

1

예제 입력 2

1 1 3

예제 출력 2

0

예제 입력 3

2 0 3

예제 출력 3

6

예제 입력 4

2 1 4

예제 출력 4

2

힌트

예제 1의 경우에 가능한 플레이리스트는 (노래1, 노래1, 노래1) 이다.

예제 2의 경우에는 가능한 플레이리스트가 없다.

예제 3의 경우에 (노래1, 노래1, 노래1), (노래2, 노래2, 노래2)는 불가능한 경우이다.

예제 4의 경우에 가능한 플레이리스트는 (노래1, 노래2, 노래1, 노래2), (노래2, 노래1, 노래2, 노래1) 이다.