Bessie 想拿 M 种颜色的长为 K 的图章涂一个长为 N 的迷之画布。假设他选择涂一段区间，则这段区间长度必须为K，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态。N\leq 10^6,M\leq 10^6,K\leq 10^6 。
对于 75\% 的数据，N,K\leq 10^3。
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 取模）
3 2 2
6
如果两个图章叫 A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB。
USACO