问题描述

有 $N$ 个球按顺序排列在一列上。用 $K$ 种颜色对球进行涂色（共有 $K^N$ 种涂色方式）。进行若干次将连续的正好 $L$ 个球进行 shift 操作，使得颜色的排列与之前相同的涂色方式被认为是相同的涂色方式。问存在多少种不同的涂色方式。其中，将球 $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$