#gw2015e. [gw2015_e]シフト塗り分け

[gw2015_e]シフト塗り分け

问题描述

NN 个球按顺序排列在一列上。用 KK 种颜色对球进行涂色(共有 KNK^N 种涂色方式)。进行若干次将连续的正好 LL 个球进行 shift 操作,使得颜色的排列与之前相同的涂色方式被认为是相同的涂色方式。问存在多少种不同的涂色方式。其中,将球 ii,球 i+1i+1,...,球 i+L1i+L-1 进行 shift 是指将这些球按照顺序重新排列为球 i+L1i+L-1,球 ii,球 i+1i+1,...,球 i+L2i+L-2


输入

输入以以下格式从标准输入中给出。

NN KK LL

  • 11 行包含 33 个整数 N(2N106)N (2 ≤ N ≤ 10^6), K(1K106)K (1 ≤ K ≤ 10^6), L(2LN)L (2 ≤ L ≤ N),以空格分隔。

输出

将不同涂色方式的种类数除以 109+710^9+7 的余数后输出为 11 行。在输出末尾添加换行符。


示例1

3 3 3

示例1输出

11

在这个例子中,存在以下 1111 种不同的涂色方式。

  • 1,1,11,1,1
  • 1,1,21,1,2
  • 1,1,31,1,3
  • 1,2,21,2,2
  • 1,2,31,2,3
  • 1,3,21,3,2
  • 1,3,31,3,3
  • 2,2,22,2,2
  • 2,2,32,2,3
  • 2,3,32,3,3
  • 3,3,33,3,3

示例2

3 3 2

示例2输出

10

在这个例子中,存在以下 1010 种不同的涂色方式。

  • 1,1,11,1,1
  • 1,1,21,1,2
  • 1,1,31,1,3
  • 1,2,21,2,2
  • 1,2,31,2,3
  • 1,3,31,3,3
  • 2,2,22,2,2
  • 2,2,32,2,3
  • 2,3,32,3,3
  • 3,3,33,3,3