Stamp Painting
提交数: 49, 通过率: 26.53%, 平均分: 57.8
题目描述:
Bessie想拿M种颜色的长为K的图章涂一个长为N的迷之画布。假设他选择涂一段区间，则这段区间长度必须为K，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，N≤106,M≤106,K≤106
对于75% 的数据，N,K≤103
输入格式:
一行3个整数N,M,K
输出格式:
一个整数表示答案（模109+7 ）
样例输入:
3 2 2
样例输出:
6
提示:
如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB
时间限制: 1000ms空间限制: 128MB
来源: Usaco2018 Jan Gold