산 풍경

각 높이가 0 이상 h 이하인 w개의 열로 이루어지고 합이 n 이하이며 모든 높이가 같지 않은 장면의 수를 10^9+7로 나눈 나머지를 구한다.

보통6동적 계획법조합론수학누적 합아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

화가에게 폭이 1인치인 리본 한 롤이 있다. 화가는 리본을 정수 길이 조각으로 자른 뒤, 액자 아래쪽 변에 맞춰 세로로 세워 열을 이루게 놓아 산 풍경을 만든다. 산 풍경은 높이가 고르지 않아야 한다. 모든 열의 높이가 같으면 그것은 평지이지 산이 아니다. 리본을 남김없이 쓸 필요는 없다.

액자는 가로가 w인치, 세로가 h인치다. 따라서 열은 왼쪽부터 차례로 w개이고, 각 열의 높이는 0 이상 h 이하의 정수다. 높이가 0인 열에는 리본을 놓지 않는다. 한 열에 조각을 두 개 이상 넣을 이유는 없으므로 각 열에는 조각을 최대 하나만 놓는다. 놓은 조각의 길이를 모두 더한 값은 n을 넘을 수 없다.

리본이 4인치이고 액자가 2 × 2인치이면 다음 풍경을 만들 수 있다.

다음 풍경은 산이 아니라 평지이므로 만들지 않는다.

리본 길이 n과 액자의 가로 w, 세로 h가 인치 단위로 주어진다. 화가가 만들 수 있는 서로 다른 산 풍경의 개수를 구하라. 리본이 덮은 영역이 다르면 두 풍경은 서로 다르다.

입력

한 줄에 공백으로 구분된 정수 세 개 n, w, h가 주어진다. n (0 ≤ n ≤ 10,000)은 리본의 길이, w (1 ≤ w ≤ 100)는 액자의 가로, h (1 ≤ h ≤ 100)는 액자의 세로이며 단위는 모두 인치다.

출력

화가가 만들 수 있는 산 풍경의 총 개수를 109+710^9 + 7로 나눈 나머지를 정수 하나로 출력한다.