 2017 Ho Chi Minh City Regional Contest #### Start

2017-12-08 01:15 UTC

## 2017 Ho Chi Minh City Regional Contest

#### End

2017-12-08 06:15 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -776 days 12:09:01

5:00:00

0:00:00

# Problem AArranging Wine

The host university is organizing a party for this year’s ACM/ICPC contestants with a buffet dinner and $R$ boxes of red wine and $W$ boxes of white wine. Wine boxes are to be arranged into non-empty piles, each pile contains only one type of wine, either white or red. After that, those piles are put into a line so that no two piles belonging to the same kind sit next to each other. In addition, for security reasons, each red wine pile should not have more than $d$ boxes of red wine, although piles of white wine can be arbitrarily large.

Your task is to identify $K$ - the number of different ways to arrange the given wine boxes satisfying all of the above conditions.

## Input

The input contains $3$ space separated integers in one line: $R$, $W$, $d$ $(1 \leq R,W \leq 10^6, 1 \leq d \leq R)$

## Output

Write in one line the remainder of $K$ divided by $10^9+7$.

## Sample Clarification

In the first sample below, there are $3$ valid arrangements: In the second sample below, there are $6$ valid arrangements: Sample Input 1 Sample Output 1
2 2 1

3

Sample Input 2 Sample Output 2
2 2 2

6