Có \(n\) viên bi giống nhau được đặt vào \(m\) cái hộp, mỗi chiếc hộp chứa được không quá \(k\) viên bi. Thứ tự đặt các hộp không quan trọng. Vì vậy, trường hợp chiếc hộp thứ nhất chứa 2 viên bi, chiếc hộp thứ hai chứa 1 viên bi được coi như là trường hợp hộp thứ nhất chứa 1 viên bi, chiếc hộp thứ hai chứa 2 viên bi.

Yêu cầu

Cho các số nguyên \(n\), \(m\) và \(k\). Hãy xác định số cách đặt khác nhau \(n\) viên bi vào \(m\) cái hộp sao cho mỗi hộp không quá \(k\) viên bi. Tức là, đếm số dãy số nguyên thỏa mãn:

\[ \begin{cases} x_1 + x_2 + \dots + x_m = n \\ 0 \le x_1 \le x_2 \le \dots \le x_m \le k \end{cases} \]

Dữ liệu

• Gồm một dòng chứa 3 số nguyên \(n\), \(m\), \(k\) (\(0 \le n, m, k \le 5000\))

Kết quả

• In ra một số nguyên là số dịnh trong phép chia: số cách tìm được chia cho \(10^9 + 7\)

Input 1

4 3 2

Output 1

2

Input 2

5 2 3

Output 2

1

Input 3

6 3 3

Output 3

3

Ràng buộc chấm điểm:

• 40% số điểm: \(n \le 200\)
• 30% số điểm: \(n \le 1000\)
• 30% số điểm: Không có ràng buộc bổ sung