A2553. Stamp Painting G
编程题
省选/NOI-
知识点
题目描述
Bessie想拿$M$ 种颜色的长为$K$ 的图章涂一个长为$N$ 的迷之画布。假设他选择涂一段区间，则这段区间长度必须为$K$ ，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，$N\leq 10^6,M\leq 10^6,K\leq 10^6$
对于$75\%$ 的数据，$N,K\leq 10^3$
对于$75\%$ 的数据，$N,K\leq 10^3$
输入格式
输入格式：
一行3个整数$N,M,K$
一行3个整数$N,M,K$
输出格式
输出格式：
一个整数表示答案（模$10^9+7$ ）
一个整数表示答案（模$10^9+7$ ）
输入输出样例
输入 #1
3 2 2
输出 #1
6
说明/提示
输入输出样例
说明
如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB
说明
如果两个图章叫A,B，合法方案如下:AAB,ABB,BAA,BBA,AAA,BBB