Stamp Painting

Bessie has an $N$ unit long strip of canvas ($1 \leq N \leq 10^6$), and she intends to paint it. She was unable to acquire any paint brushes. In their place she has $M$ rubber stamps of different colors ($1 \leq M \leq 10^6$), each stamp $K$ units wide ($1 \leq K \leq 10^6$). She wants to know exactly how many different paintings she could create by stamping her stamps on the canvas in some order.

To use a stamp, align it with exactly $K$ neighboring units of the canvas. The stamp cannot extend beyond the ends of the canvas, and it cannot cover a fraction of a unit. Once placed, the stamp paints the $K$ covered units with its color. Any given stamp may be used many times, once, or never at all. By the time Bessie is finished, every unit of the canvas must have been painted at least once.

Count the paintings Bessie could produce, modulo $10^9 + 7$. Two paintings that look identical but were made by different sequences of stamping operations count as the same painting.

The first and only line has three integers $N$, $M$, and $K$, separated by spaces. It is guaranteed that $K \leq N$.

Print the number of possible paintings, modulo $10^9 + 7$, on one line.

With $N = 3$, $M = 2$, $K = 2$ and stamp colors A and B, the possible paintings are AAA, AAB, ABB, BAA, BBA, BBB, which is 6 of them.