Bessie は長さ $N$ 単位のキャンバス（$1 \leq N \leq 10^6$）を手に入れ、絵を描こうとしています。しかし筆を入手できず、代わりに色の異なる $M$ 個のゴムスタンプ（$1 \leq M \leq 10^6$）があり、各幅は $K$ 単位です（$1 \leq K \leq 10^6$）。可能性の多さに驚き、ある順番でスタンプを押して何種類の絵を作れるかを知りたいと思っています。

スタンプを使うには、キャンバスのちょうど $K$ 個の連続する単位に合わせます。両端からはみ出したり単位の一部分を覆ったりはできません。置くと覆われた $K$ 単位をその色に塗ります。各スタンプは何度も、一度だけ、または全く使わなくても構いません。ただし Bessie が終える時、全ての単位が少なくとも一度塗られていなければなりません。

Bessie を手伝って絵の種類数を $10^9 + 7$ で割った余りを求めてください。押す操作の順序が違っても見た目が同じ絵は同一と数えます。

入力

唯一の入力行に三整数 $N$、$M$、$K$ が与えられます。$K \leq N$ が保証されます。

出力

一つの整数、絵の種類数を $10^9 + 7$ で割った余りです。

入出力例

入力 1

3 2 2

出力 1

6

注記

二つのスタンプが色 A と B なら、可能な絵は AAA、AAB、ABB、BAA、BBA、BBB です。

小課題

少なくとも $75\%$ の入力ケースでは $N,K \leq 10^3$ です。

作問：Dhruv Rohatgi