Problem Statement

MAK's hobby is collecting arrays.

Every day, MAK goes to the array grounds, a place where arrays can be obtained, and devotes himself to searching for arrays. Every array obtained at the array grounds has length $N$, and all of its elements have the value $1$. Since MAK can only carry arrays of length less than $K$, he repeats the following operation until the length of the array obtained at the array grounds becomes less than $K$. Here, let $A$ be the array before the operation. Also, let $A_i$ denote the value of the $i$-th element of array $A$, where array indices are 1-indexed.

- Remove a contiguous subarray $B$ of length $K$ from $A$, and insert a new value $x =D\times B_1\times B_2\times \dots \times B_K$ at the place where it was removed.

For example, if $A=\{ 2,2,1,3,1 \}$ and $K=3、D=2$, operating on the interval $2 \le i \le 4$ gives $A=\{ 2,12,1 \}$, and operating on the interval $3 \le i \le 5$ gives $A=\{ 2,2,6 \}$.

An array whose length has become less than $K$ and which can thus be carried is stored in MAK's array collection (Array Collection, commonly known as AC). However, since MAK is only interested in new things, if an array identical in all elements is already stored in the array collection, he exchanges the carried array for cash and keeps it as his pocket money. MAK has collected arrays so many times that he has gathered all the arrays that can be obtained.

MAK became curious about the total sum of all elements of all arrays stored in the array collection, that is, the value of $\displaystyle \sum_{ A \in S } \displaystyle \sum^L_{i=1} A_i$, where $S$ is the set of arrays stored in the array collection and $L$ is the length of the array. Since this value can be very large, output the remainder when it is divided by $1{,}000{,}000{,}007=10^9+7$.

Input

$N\ K\ D$

$2\leq N\leq 10^6, 2\leq K\leq N, 1\leq D\leq 10^6$
$N,K,D$ are integers.

Output

Output the remainder when the total sum of all elements of all arrays stored in the array collection is divided by $1{,}000{,}000{,}007$. Print a newline at the end.

Sample

8 4 2

14

8 4 1

2

12345 67 89

967411319