P4187 [USACO18JAN] Stamp Painting G

Bessie想拿$M$ 种颜色的长为$K$ 的图章涂一个长为$N$ 的迷之画布。假设他选择涂一段区间，则这段区间长度必须为$K$ ，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，$N\leq 10^6,M\leq 10^6,K\leq 10^6$ 对于$75\%$ 的数据，$N,K\leq 10^3$

无

无

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