Để độ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 vừa qua, 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 VUI NHỘN 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,
sao cho cô sẽ mua \(n\) chiếc áo, và với mỗi màu áo từ \(1\) đến \(k\) xuất hiện ít nhất \(m\) lần trong \(n\) chiếc áo.
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é.

Input

• Một dòng chứa 3 số nguyên dương \(n, k, m (1 \le k \le n, m ∗ 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 mod \(10^9 + 7\).

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 $
• Subtask \(4\) (\(10\%\) số điểm): \(n \le m ∗ 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\)

Example

3 2 1

6

4 2 2

6