A2553 | $Stamp Painting G$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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$ ）

输入 #1

3 2 2

输出 #1

C++ 编辑器

输入

输出