Bessie 有一條長 $N$ 單位的畫布（$1 \leq N \leq 10^6$），打算作畫，卻沒能找到畫筆。她有 $M$ 枚顏色不同的橡膠印章（$1 \leq M \leq 10^6$）代替畫筆，每枚寬 $K$ 單位（$1 \leq K \leq 10^6$）。眼前的各種可能令她驚嘆，她想知道按照某個順序在畫布上蓋章，究竟能畫出多少種不同的畫。

使用印章時，必須先對齊畫布上恰好 $K$ 個相鄰單位。印章不能超出畫布兩端，也不能只覆蓋某個單位的一部分。放好後，它將所覆蓋的 $K$ 個單位塗成其顏色。每枚印章可以用多次、一次，甚至完全不用。但 Bessie 完成時，每個畫布單位都必須至少塗過一次。

幫助 Bessie 求不同畫的數量，對 $10^9 + 7$ 取模。外觀相同但蓋章操作順序不同的兩幅畫算作同一種。

輸入格式

輸入僅有一行，包含三個整數 $N$、$M$ 和 $K$。保證 $K \leq N$。

輸出格式

一個整數：可能的畫的數量，對 $10^9 + 7$ 取模。

範例

輸入格式 1

3 2 2

輸出格式 1

6

說明

若兩枚印章顏色為 A 和 B，可能的畫為 AAA、AAB、ABB、BAA、BBA 和 BBB。

子任務

至少 $75\%$ 的輸入資料滿足 $N,K \leq 10^3$。

題目來源：Dhruv Rohatgi