Problem Description

There are $ N $ balls arranged in a row. We will color these balls with $ K $ different colors (there are $ K^N $ ways to color them). We consider two colorings to be the same if we can make their color sequences identical by repeatedly shifting exactly $ L $ consecutive balls. By shifting balls $ i $, $ i+1 $, ... $ i+L-1 $, we mean rearranging them to be $ i+L-1 $, $ i $, $ i+1 $, ... $ i+L-2 $. How many distinct colorings are there?

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ L $

• The first line contains three integers $N\ (2\ ≦\ N\ ≦\ 10^6),\ K\ (1\ ≦\ K\ ≦\ 10^6),\ L\ (2\ ≦\ L\ ≦\ N)$ separated by spaces.

Output Format

Output the number of distinct colorings modulo $ 10^9+7 $ in one line. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 3 3

Sample Output #1

11

Sample Input #2

3 3 2

Sample Output #2

10

Notes/Hints

Sample Explanation 1

In this example, there are $ 11 $ distinct colorings as follows: - $ 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

In this example, there are $ 10 $ distinct colorings as follows: - $ 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 $

见题面 Input 部分

见题面 Output 部分