問題文

MAK君の趣味は配列集めです。

MAK君は毎日、配列場という配列を取ることができる場所に行き、配列探しに明け暮れています。配列場で取れる配列は全て長さが$N$で、全ての要素の値が$1$となっています。MAK君は長さが$K$より小さい配列しか運ぶことができないため、配列場で得られた配列の長さが$K$より小さくなるまで以下の操作を行います。ただし、操作前の配列を$A$とします。また、配列$A$における$i$番目の要素の値を$A_i$と表すことにして、配列の番号は 1-indexed とします。

・$A$から長さ$K$の連続な部分配列$B$を取り除き、取り除いた部分に新たな値 $x =D\times B_1\times B_2\times \dots \times B_K$ を挿入する。

例えば、$A=\{ 2,2,1,3,1 \}$で$K=3、D=2$の場合、区間 $2 \le i \le 4$ について操作すると、$A=\{ 2,12,1 \}$、区間 $3 \le i \le 5$ について操作すると、$A=\{ 2,2,6 \}$になります。

長さが$K$よりも小さくなり、運べるようになった配列はMAK君の配列コレクション(Array Collection：通称 AC)に収納されます。しかし、MAK君は新しいものしか興味を示さないため、既に各要素が全て同じ配列が配列コレクションに収納されている場合、運ばれた配列は換金して自分のお小遣いにします。MAK君は配列集めを何回もしたため、得ることが可能な配列はすべて集めました。

MAK君は、配列コレクションに収納されている全ての配列の各要素の総和、すなわち、配列コレクションに収納されている配列の集合を$S$、配列の長さを$L$としたときの$\displaystyle \sum_{ A \in S } \displaystyle \sum^L_{i=1} A_i$ の値がどのようになっているのか気になりました。この値は非常に大きくなる場合があるため、$1{,}000{,}000{,}007=10^9+7$ で割ったときの余りを出力してください。

入力

$N\ K\ D$

$2\leq N\leq 10^6, 2\leq K\leq N, 1\leq D\leq 10^6$
$N,K,D$は整数

出力

配列コレクションに収納されている全ての配列の各要素の総和を$1{,}000{,}000{,}007$で割ったときの余りを出力してください。最後に改行してください。

サンプル

8 4 2

14

8 4 1

2

12345 67 89

967411319