题目描述

现在有 $N$ 个球并排排成一列。用 $K$ 种不同的颜色为这些球着色（共有 $K^N$ 种不同的绘画方式）。只是对于两个绘画方式，如果多次的对其中的连续的 $L$ 个球进行 shift 操作后相同，那么我们就认为它们是是相同的。现在问你对于给定的 $N , M , K$ 有几种不同的绘画方式。

对于球 $i$ $,$ 球 $i+1$ $,$ $...$ 球 $i+L-1$ 这任意连续 $L$ 个球，一次 shift 操作后就变为 球 $i+L-1$ $,$ 球 $i$ $,$ 球 $i+1$ $,$ $...$ 球 $i+L-2$。(译者注：一次 shift 操作就是选定连续的$L$个球然后把选定的球中最后的那个球放到最前面，其他球依次往后移动一位)

输入格式

输入来自标准输入，格式如下：

 $ N $   $ K $   $ L $ 

输入共一行，第一行依次给出三个整数 $N ( 2 \leq N \leq 10^6), K (1 \leq K \leq 10^6), L (2 \leq L \leq N)$

输出格式

输出共一行，你需要输出总方法数对于 $10^9+7$ 取模后的值。输出末尾需要换行。

说明/提示

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

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