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$。
输入格式
一行三个整数 $N,M,K$。
输出格式
一个整数表示答案（对 $10^9+7$ 取模）
说明/提示
输入输出样例说明
如果两个图章叫 A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB。
Translated by @ComeIntoPower