Zhautykov Olympiad 2020 Azerbaijan National Team Selection Contest Revisited

Happy ending with happy painting

After the police caught Barish, they fined him. Barish has found himself in possession of an N-unit long strip of canvas ( 1N106), and he intends to paint it. However, he has been unable to acquire paint brushes. In their place he has M rubber stamps of different colors (1M106 ), each stamp K units wide (1K106 ). Astounded by the possibilities that lie before him, he wishes to know exactly how many different paintings he could conceivably create, by stamping his stamps in some order on the canvas. To use a stamp, it must first be aligned with exactly K neighboring units on 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 K covered units with its color. Any given stamp may be used multiple times, once, or even never at all. But by the time Barish is finished, every unit of canvas must have been painted at least once. Help Barish find the number of different paintings that he could paint, modulo 109+7. Two paintings that look identical but were painted by different sequences of stamping operations are counted as the same.


The numbers N, M, K are given in the first line. KN .

Output format:

A single integer: the number of possible paintings, modulo 109 + 7 .

Explanation for first test case

If the two stamps have colors A and B, the possible paintings are AAA, AAB,ABB, BAA, BBA, and BBB.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 2 2
Output example #1
Source IZHO 2019-2020 Azerbaijan selection contest