Hãy đếm xem có bao nhiêu mảng khác nhau ~a_1, a_2, \dots, a_n~ trong đó ~a_i~ nhận các giá trị nguyên dương trong đoạn ~[1, M]~ sao cho tồn tại ít nhất một đoạn ~K~ giá trị liên tiếp giống nhau. Ở đây hai mảng được gọi là khác nhau nếu như tồn tại ít nhất một vị trí mà giá trị phần tử hai mảng ở vị trí này là khác nhau.

Yêu cầu: Tính số lượng mảng thỏa mãn điều kiện trên, kết quả lấy phần dư khi chia cho ~10^9 + 7~.

Input

• Một dòng duy nhất chứa ba số nguyên dương ~n, M, K~ (~1 \le n, M, K \le 10^6~)

Output

• Ghi ra một số nguyên duy nhất là số lượng mảng tìm được sau khi lấy phần dư cho ~10^9 + 7~.