← 返回题目列表

AtCoder · gw2015_e

E. 移位着色

中文机器翻译题面 查看原题

問題文

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