問題文
N 球 1 排队。K 给球涂上不同的颜色(K^N 有不同的绘画方式)。只是连续的 L 球 转变 您可以重复此操作几次以使颜色排列相同。 2 当我们将两种绘画方式视为同一种绘画方式时,存在多少种不同的绘画方式?然而,球 i, 球 i+1, ... 球 移动 i+L-1 意味着将这些球移动到 i+L-1, 球 i, 球 i+1, ... 球 移动 i+L-2 是排序操作。
入力
输入将以以下格式从标准输入提供。
N K L
- 1 第几行包含,3 整数 N (2 ≦ N ≦ 10^6), K (1 ≦ K ≦ 10^6), L (2 ≦ L ≦ N) 用空格分隔。
出力
不同绘画方法的数量 除以 10^9+7 后的余数 在 1 行输出。在输出末尾插入换行符。
入力例1
3 3 3
出力例1
11
在此示例中,以下内容 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
3 3 2
出力例2
10
在此示例中,以下内容 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