시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB129560745047.872%

문제

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

  • 모든 노래를 플레이리스트에 추가해야 한다.
  • 같은 노래를 추가하려면, 플레이리스트에서 두 노래 사이에 적어도 M개의 곡이 있어야 한다.

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

입력

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

출력

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

예제 입력 1

1 0 3

예제 출력 1

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) 이다.

출처