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

Input

5 2 1

Output

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

Input

5 2 0

Output

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

Input

5 1 10

Output

5

Explanation

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