시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 55 10 8 21.053%

문제

세 정수 $N$, $K$, $D$가 주어졌을 때, 다음 조건을 만족하는 크기가 $K$인 자연수 수열 $A_1, A_2, \dots, A_K$의 개수를 구해보자.

  • $A_1 + A_2 + \dots + A_K = N$
  • $A_1 < A_2 < \dots < A_K$
  • $A_{i+1} - A_i \le D$ $(1 \le i < K)$
  • $A_1 \le D$

입력

첫째 줄에 $N$, $K$, $D$가 주어진다.

출력

문제 조건을 만족하는 수열의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

제한

  • $1 \le N, K, D \le 10^5$

예제 입력 1

10 4 1

예제 출력 1

1