AT_gw2015_e シフト塗り分け

[problemUrl]: https://atcoder.jp/contests/gwcontest2015/tasks/gw2015_e $ 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 $ 行に出力せよ。出力の末尾に改行を入れること。

### Sample Explanation 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 $ ### Sample Explanation 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 $