84412 - Stamp Painting
时间限制 : 1 秒
内存限制 : 128 MB
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