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$

输入格式

一行3个整数$N,M,K$

输出格式

一个整数表示答案（模$10^9+7$ ）

输入输出样例

说明

如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB

Translated by @ComeIntoPower

输入输出样例 1

3 2 2

6