Stamp Painting#10425
Bessie has come into possession of an -unit-long strip of canvas, and she intends to paint it. However, she has been unable to get hold of any paintbrushes. Instead, she has rubber stamps of different colors, each units wide. Astounded by the possibilities before her, she wishes to know exactly how many different paintings she could create by stamping her stamps on the canvas in some order.
To use a stamp, Bessie must first align it with exactly consecutive units of the canvas. The stamp cannot extend beyond the ends of the canvas, nor can it cover fractions of units. Once placed, the stamp paints the covered units with its color. Any stamp may be used several times, once, or not at all. However, by the time Bessie has finished, every unit of the canvas must have been painted at least once.
Help Bessie find the number of different paintings she could create, modulo 10^9 + 7. Two paintings that look identical are counted as the same, even if they were produced by different sequences of stamping operations.
Three integers , and k~(1 \le n \le 10^6, 1 \le m \le 10^6, 1 \le k \le n).
Print the number of possible paintings modulo 10^9 + 7.
Example 1
In the example, there are two stamps with colors A and B, and the possible paintings are AAA, AAB, ABB, BAA, BBA and BBB.