Stamp Painting

题目描述

Bessie 现在有一条长度为 $N$ 个单位的画布条 ($1 \leq N \leq 10^6$)，她打算给它上色。然而，她一直没能弄到画笔。作为替代，她有 $M$ 个不同颜色的橡皮图章（$1 \leq M \leq 10^6$），每个图章的宽度为 $K$ 个单位 ($1 \leq K \leq 10^6$)。面对这些可能性，她想知道：通过以某种顺序在画布上盖这些图章，她一共可能创造出多少种不同的画作。 要使用一个图章，必须先将它与画布上恰好 $K$ 个相邻单位对齐。图章不能超出画布的两端，也不能覆盖单位的一部分。放置后，图章会将覆盖的 $K$ 个单位涂成其颜色。任意一个图章都可以使用多次、只用一次，甚至一次也不用。但当 Bessie 完成时，画布的每个单位都必须至少被涂过一次。 请帮助 Bessie 计算她可以画出的不同画作数量，对 $10^9 + 7$ 取模。两幅看起来相同但由不同盖章操作序列得到的画作，视为同一种。 对于至少 75% 的测试点，$N,K \leq 10^3$。

输入格式

第一行也是唯一一行输入包含三个整数 $N$、$M$ 和 $K$。保证 $K \leq N$。

输出格式

输出一个整数：可能的画作数量，对 $10^9 + 7$ 取模。

3 2 2

6

提示

如果两个图章的颜色分别为 A 和 B，则可能的画作是 AAA、AAB、ABB、 BAA、BBA 和 BBB。 题目来源：Dhruv Rohatgi

标签: USACO|2018|Gold

来源

USACO|2018|Gold