問題文

$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$