Bessie đang sở hữu một dải vải bạt dài \(N\) đơn vị (\(1 \leq N \leq 10^6\)) và cô muốn tô màu nó. Tuy nhiên, cô không thể kiếm được cọ vẽ. Thay vào đó, cô có \(M\) con dấu cao su mang các màu khác nhau (\(1 \leq M \leq 10^6\)), mỗi con dấu rộng \(K\) đơn vị (\(1 \leq K \leq 10^6\)). Kinh ngạc trước vô vàn khả năng trước mắt, cô muốn biết chính xác mình có thể tạo ra bao nhiêu bức tranh khác nhau bằng cách đóng các con dấu lên tấm vải theo một thứ tự nào đó.

Để sử dụng một con dấu, trước tiên phải căn nó khớp chính xác với \(K\) đơn vị liền kề trên tấm vải. Con dấu không được vượt ra ngoài hai đầu tấm vải và cũng không được phủ lên một phần lẻ của một đơn vị. Sau khi được đặt xuống, con dấu tô \(K\) đơn vị mà nó phủ bằng màu của mình. Mỗi con dấu có thể được sử dụng nhiều lần, đúng một lần hoặc hoàn toàn không được sử dụng. Tuy nhiên, khi Bessie hoàn tất, mọi đơn vị trên tấm vải đều phải được tô ít nhất một lần.

Hãy giúp Bessie tìm số bức tranh khác nhau mà cô có thể tô, lấy phần dư theo \(10^9+7\). Hai bức tranh trông giống hệt nhau nhưng được tạo bởi các chuỗi thao tác đóng dấu khác nhau vẫn được tính là cùng một bức tranh.

Phân nhóm

Trong ít nhất \(75\%\) số bộ dữ liệu vào, \(N,K \leq 10^3\).

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên \(N\), \(M\) và \(K\). Dữ liệu đảm bảo \(K \leq N\).

Dữ liệu ra

In ra một số nguyên duy nhất: số bức tranh có thể tạo ra, lấy phần dư theo \(10^9+7\).

Ví dụ

3 2 2

6

Nguồn

USACO 2018 January Contest, Gold — Stamp Painting

Tác giả bài toán: Dhruv Rohatgi.