Bessie besitzt einen $N$ Einheiten langen Leinwandstreifen ($1 \leq N \leq 10^6$) und möchte ihn bemalen, konnte aber keine Pinsel beschaffen. Stattdessen hat sie $M$ Gummistempel verschiedener Farben ($1 \leq M \leq 10^6$), jeder $K$ Einheiten breit ($1 \leq K \leq 10^6$). Begeistert von den Möglichkeiten will sie genau wissen, wie viele verschiedene Bilder sie durch Stempeln in irgendeiner Reihenfolge erzeugen kann.

Ein Stempel muss genau an $K$ benachbarten Einheiten ausgerichtet werden. Er darf weder über die Enden hinausragen noch Bruchteile von Einheiten bedecken. Er färbt die $K$ bedeckten Einheiten in seiner Farbe. Jeder Stempel darf mehrfach, einmal oder gar nicht verwendet werden. Am Ende muss jedoch jede Einheit mindestens einmal bemalt sein.

Hilf Bessie, die Zahl verschiedener Bilder modulo $10^9 + 7$ zu bestimmen. Gleich aussehende Bilder aus unterschiedlichen Stempelfolgen zählen als dasselbe.

Eingabe

Die einzige Zeile enthält drei ganze Zahlen $N$, $M$ und $K$. Es gilt garantiert $K \leq N$.

Ausgabe

Eine ganze Zahl: die Zahl möglicher Bilder modulo $10^9 + 7$.

Beispiele

Eingabe 1

3 2 2

Ausgabe 1

6

Hinweis

Haben die zwei Stempel die Farben A und B, sind AAA, AAB, ABB, BAA, BBA und BBB möglich.

Teilaufgaben

Für mindestens $75\%$ der Eingabefälle gilt $N,K \leq 10^3$.

Aufgabenautor: Dhruv Rohatgi