Ivan có \(n\) viên kẹo đôi một khác nhau và cần xếp chúng vào đúng \(k\) hộp giống hệt nhau. Mỗi hộp không rỗng, mỗi viên kẹo thuộc đúng một hộp. Thứ tự các hộp không quan trọng, nhưng thứ tự các viên trong một hộp có ý nghĩa; viên lớn nhất của mỗi hộp phải đứng đầu hộp đó. Hãy đếm số cách xếp, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng duy nhất chứa \(n,k\) (\(1\le n\le5000\), \(1\le k\le n\)).

Dữ liệu ra

In số cách xếp hợp lệ theo modulo \(10^9+7\).

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(8\) điểm: \(k=1\).
2. \(19\) điểm: \(k=2\).
3. \(14\) điểm: \(n\le10\).
4. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

3 1

2

3 2

3

4 2

11

Nguồn

COCI 2025/2026 - Vòng 3, bài Festival.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.