HANGRAO Dựng hàng rào

 Tom và Jerry mới mua được một trang trại ở ngoại ô rất đẹp, phía trước và 2 bên của trang trại đã có cổng và được rào rất chắc chắn. Để đảm bảo an ninh cho trang trại của mình, Tom và Jerry quyết định làm hàng rào dài N đơn vị ở phía mặt sau trang trại. Hai anh em có rất nhiều thanh gỗ, mỗi thanh đều dài K đơn vị và mang một trong M màu khác nhau.

            Tom và Jerry chọn ra các thanh gỗ và xếp liên tiếp với nhau để thành hàng rào. Tổng độ dài các thanh gỗ có thể vượt quá N. Khi đó họ sẽ cưa bớt thanh cuối cùng để được độ dài đúng bằng N.

            Yêu cầu: Hãy giúp họ tìm số lượng cách dựng hàng rào có màu sắc khác nhau.  Hai hàng rào dù được ghép bởi các thanh gỗ khác nhau nhưng trông giống hệt nhau về màu sắc được tính là như nhau. Số lượng thanh gỗ thuộc mỗi màu có thể xem là vô hạn.

Input: ghi ba số nguyên N, M và K (1 ≤ N ≤ 10⁶; 1 ≤ K ≤ N; 1 ≤  M ≤ 10⁶)

Output: ghi một số nguyên duy nhất là số cách dựng hàng rào có màu sắc khác nhau. Kết quả được modulo cho (10⁹ + 7).

Input	Output
4 2 3	6

 

Giải thích: Nếu hai thanh gỗ lần lượt có màu 1 và 2, các hàng rào có thể là: