One day, my grandmas left N cookies. My elder sister and I were going to eat them immediately, but there was the instruction. It said

• Cookies will go bad; you should eat all of them within D days.
• Be careful about overeating; you should eat strictly less than X cookies in a day.

My sister said “How many ways are there to eat all of the cookies? Let's try counting!”

Two ways are considered different if there exists a day such that the numbers of the cookies eaten on that day are different in the two ways. For example, if N, D and X are 5, 2 and 5 respectively, the number of the ways is 4:

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

I noticed the number of the ways would be very huge and my sister would die before counting it. Therefore, I tried to count it by a computer program to save the life of my sister.

Input format

The input consists of multiple datasets. The number of datasets is no more than 100. For each dataset, three numbers N (1 \leq N \leq 2{,}000), D (1 \leq D \leq 10^{12}) and X (1\leq X\leq 2{,}000) are written in a line and separated by a space. The end of input is denoted by a line that contains three zeros.

Output format

Print the number of the ways modulo 1{,}000{,}000{,}007 in a line for each dataset.
Sample

Input:

5 2 5
3 3 3
5 4 5
4 1 2
1 5 1
1250 50 50
0 0 0

Output:

4
7
52
0
0
563144298