问题描述
有 N 个球按顺序排列在一列上。用 K 种颜色对球进行涂色(共有 KN 种涂色方式)。进行若干次将连续的正好 L 个球进行 shift 操作,使得颜色的排列与之前相同的涂色方式被认为是相同的涂色方式。问存在多少种不同的涂色方式。其中,将球 i,球 i+1,...,球 i+L−1 进行 shift 是指将这些球按照顺序重新排列为球 i+L−1,球 i,球 i+1,...,球 i+L−2。
输入
输入以以下格式从标准输入中给出。
N K L
- 第 1 行包含 3 个整数 N(2≤N≤106), K(1≤K≤106), L(2≤L≤N),以空格分隔。
输出
将不同涂色方式的种类数除以 109+7 的余数后输出为 1 行。在输出末尾添加换行符。
示例1
示例1输出
在这个例子中,存在以下 11 种不同的涂色方式。
- 1,1,1
- 1,1,2
- 1,1,3
- 1,2,2
- 1,2,3
- 1,3,2
- 1,3,3
- 2,2,2
- 2,2,3
- 2,3,3
- 3,3,3
示例2
示例2输出
在这个例子中,存在以下 10 种不同的涂色方式。
- 1,1,1
- 1,1,2
- 1,1,3
- 1,2,2
- 1,2,3
- 1,3,3
- 2,2,2
- 2,2,3
- 2,3,3
- 3,3,3