Cookie Counter

Grandma left $N$ cookies behind. My elder sister and I wanted to eat them right away, but a note was attached to the box.

• The cookies go bad, so all of them have to be eaten within $D$ days.
• Overeating is bad for you, so the number eaten on a single day has to be strictly less than $X$.

My sister asked, "How many ways are there to eat all of the cookies? Let's count them!"

One way is the list of how many cookies are eaten on day $1$, day $2$, and so on through day $D$. Each daily amount is at least $0$ and less than $X$, and the $D$ amounts add up to exactly $N$. A day with no cookies at all is allowed. Two ways are different if there is a day on which the numbers of cookies eaten differ.

For example, if $N$, $D$ and $X$ are $5$, $2$ and $5$, there are 4 ways.

• Eat 1 cookie on the first day and 4 cookies on the second day.
• Eat 2 cookies on the first day and 3 cookies on the second day.
• Eat 3 cookies on the first day and 2 cookies on the second day.
• Eat 4 cookies on the first day and 1 cookie on the second day.

The number of ways gets very large, so counting by hand is hopeless. Write a program that counts it instead.

The input consists of several datasets. There are at most 100 datasets. Each dataset is one line holding three integers $N$ ($1 \le N \le 2000$), $D$ ($1 \le D \le 10^{12}$) and $X$ ($1 \le X \le 2000$), separated by spaces. The end of the input is a line containing three zeros, and that line is not processed.

For each dataset, print the number of ways modulo $1000000007$ on its own line.