Bessie's Rubber Stamp Painting

Bessie has found herself in possession of a canvas strip of N units in length and M rubber stamps available in different colors. Each stamp is exactly K units wide. She wishes to paint the entire canvas by stamping – however, every stamp must be placed so that it covers exactly K consecutive units, and no stamp may extend past the canvas boundaries. A stamp may be used any number of times (including not at all), but by the end every unit of the canvas must have been painted at least once.

When a stamp is applied it paints the K covered units entirely in its chosen color. If a canvas unit is painted multiple times, the color from the stamp applied later in the process is the one that is visible on the final painting. Two paintings that look identical are considered the same even if they were produced by different sequences of stamp applications.

It can be shown that if Bessie uses a minimal cover of stamps placed consecutively at positions 1, 2, \(\ldots, L\) (where \(L = N-K+1\)), then the final painting is completely determined by the colors chosen for these stamps together with the ordering between each adjacent pair. In particular, for each adjacent pair of stamps:

• If the stamps have the same color, there is exactly 1 possible outcome.
• If they have different colors, there are 2 distinct outcomes depending on which stamp is applied later.

Thus, the total number of distinct paintings is given by the formula:

Note that when \(N = K\) the exponent is 0 and the answer is simply \(M\). For at least 75% of the cases, \(N, K \le 10^3\), though \(N\), \(M\) and \(K\) can be as large as \(10^6\) in general.

inputFormat

The input consists of a single line containing three integers N, M and K separated by spaces:

• \(1 \le N \le 10^6\): the length of the canvas.
• \(1 \le M \le 10^6\): the number of rubber stamps (colors) available.
• \(1 \le K \le 10^6\): the width of each stamp.

outputFormat

Output a single integer, the number of distinct paintings Bessie can produce, taken modulo \(10^9+7\).

sample

3 3 2

15