Quà kỷ niệm

Để động viên các bạn học sinh trong lớp học VUI NHỘN nhân dịp lớp đoạt chức vô địch giải bóng đá cấp trường, cô Mười Ba dự định sẽ mua tặng các học sinh của mình những chiếc áo LV mới nhất.

Lớp học có \(n\) học sinh. Cửa hàng cô dự định đến có bán \(k\) màu áo khác nhau. Cô Mười Ba muốn mua \(n\) chiếc áo cho \(n\) học sinh của mình, đồng thời cô cũng muốn với mỗi màu áo từ \(1\) đến \(k\), sẽ có ít nhất \(m\) bạn mặc chiếc áo có màu này.

Ông chủ cửa hàng rất thích toán, vì vậy ông đố cô rằng có bao nhiêu cách mua áo khác nhau. Vì bận tính tiền nên cô không thể tập trung giải quyết bài toán, bạn hãy giúp cô giải bài này để được giảm giá nhé.

Tính số cách mua \(n\) chiếc áo từ \(k\) màu có sẵn, sao cho mỗi màu áo được mua ít nhất \(m\) lần.

Input

Một dòng chứa 3 số nguyên dương \(n, k, m\) (\(1 \le k \le n, m \times k \le n \le 10^6, 1 \le m \le 2\)).

Output

Số cách chia thỏa mãn yêu cầu đề bài sau khi lấy phần dư cho \(10^9 + 7\).

Example

3 2 1

6

4 2 2

6

Scoring

• Subtask 1 (10% số điểm): \(n \le 10, k \le 5\).
• Subtask 2 (20% số điểm): \(n \le 100, k \le 10\).
• Subtask 3 (20% số điểm): \(n \le 3000, k \le 1000\).
• Subtask 4 (10% số điểm): \(n \le m \times k + 1\).
• Subtask 5 (20% số điểm): \(n \le 10^6, k \le 10^6, m = 1\).
• Subtask 6 (20% số điểm): \(n \le 10^6, k \le 3000, m = 2\).