E - シフト塗り分け Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個のボールが 1 列に並んでいる。K 種類の色でボールを塗り分ける（K^N 通りの塗り方がある）。連続するちょうど L 個のボールを shift させることを何回か繰り返して色の並びを同じにできるような 2 つの塗り方を同じ塗り方だとみなすとき、何種類の異なる塗り方が存在するだろうか。ただし、ボール i, ボール i+1, ... ボール i+L-1 を shift させるとは、これらのボールをボール 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