Hãy đếm xem có bao nhiêu mảng khác nhau \(a_1,a_2,...,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.

Input

• Một dòng duy nhất chứa ba số nguyên dương lần lượt là \(n, M, K\).

Output

• Ghi ra một số nguyên duy nhất là số lượng mảng khác nhau tìm được. Con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho \(10^9+7\).

Constants

• \(1\leq n,M,K\leq10^6\).

3 2 2 

6