$N$ 个球排成一行。你可以执行一种称为“移位”（Shift）的操作。

移位操作：选择 $L$ 个连续的球，并将所选球中最右侧的一个移动到所选球中最左侧的一个的左边。换句话说，如果你选择了位置 $i, i+1, \dots, i+L-1$ 处的球，操作后这些球将移动到位置 $i+L-1, i, i+1, \dots, i+L-2$。

你想要用 $K$ 种颜色给这些球染色。如果两种染色方案可以通过重复执行零次或多次“移位”操作相互转化，则认为它们是等价的。请计算有多少种本质不同的染色方案，结果对 $10^9 + 7$ 取模。

$N, K, L$

• $2 \le N \le 10^6$
• $1 \le K \le 10^6$
• $2 \le L \le N$

输出本质不同的染色方案数，对 $10^9 + 7$ 取模。

样例

输入格式 1

3 3 3

输出格式 1

11

输入格式 2

3 3 2

输出格式 2

10

说明

在样例 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)$。

样例 1