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 Bessie is finished, every unit of canvas must have been painted at least once.
Help Bessie find the number of different paintings that she could paint, modulo 109+7. Two paintings that look identical but were painted by different sequences of stamping operations are counted as the same.
For at least 75% of the input cases, N,K≤103.
Bessie想拿MM 种颜色的长为KK 的图章涂一个长为NN 的迷之画布。假设他选择涂一段区间，则这段区间长度必须为KK ，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，N\leq 10^6,M\leq 10^6,K\leq 10^6N≤106,M≤106,K≤106
对于75\%75% 的数据，N,K\leq 10^3N,K≤103
输入输出格式
输入格式：
一行3个整数N,M,KN,M,K
输出格式：
一个整数表示答案（模10^9+7109+7 ）
输入输出样例
说明
如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB
Translated by @ComeIntoPower
3 2 26