题目描述

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。

Translated by @ComeIntoPower