Lecture Gap

You are scheduling $k$ lectures on days $1, 2, \ldots, n$. Let $x_i$ be the day of the $i$-th lecture. The days must satisfy

$1 \le x_1, x_2, \ldots, x_k \le n$

and consecutive lectures must be at least $g$ days apart:

$x_{i+1} \ge x_i + g$

for every $i$. (In particular the sequence is automatically non-decreasing. If $g = 0$, two lectures may share a day.)

Count the number of integer sequences $x$ that meet these conditions. Since the answer can be large, output it modulo $10^9 + 7$.

Input

A single line containing three integers $n$, $k$, and $g$.

Output

Print one integer: the number of valid lecture schedules, modulo $10^9 + 7$.

Constraints

• $1 \le k \le 10^6$
• $1 \le n \le 10^6$
• $0 \le g \le 10^9$

Example 1

5 2 1

10

Explanation

Consecutive lectures must fall on strictly later days. The valid pairs $(x_1, x_2)$ are all $1 \le x_1 < x_2 \le 5$, and there are $\binom{5}{2} = 10$ of them.

Example 2

5 2 0

15

Explanation

Now lectures may share a day, so the condition is $1 \le x_1 \le x_2 \le 5$. There are $\binom{5 + 2 - 1}{2} = 15$ such pairs.

Example 3

5 1 10

5

Explanation

A single lecture can be placed on any of the $5$ days. The gap $g$ is unused when $k = 1$.