Để chuẩn bị đón giáng sinh năm 2023, Tí quyết định trích tiền tiết kiệm để mua bóng đèn trang trí và tự tay mình thiết kế một dàn đèn thật hoành tráng. Dàn đèn được Tí lắp đặt nối tiếp thành một dãy gồm \(n\) bóng. Màu của mỗi bóng đèn khi phát sáng là: đỏ hoặc xanh. Lúc phát sáng, Tí thích nhất khi thấy dãy \(n\) bóng đèn có đúng \(k\) bóng đèn (không nhất thiết liên tiếp nhau) phát màu đỏ.

Yêu cầu: Cho dãy gồm \(n\) bóng đèn mắc nối tiếp, tính số trạng thái khác nhau của dãy bóng đèn khi phát sáng có đúng \(k\) bóng màu đỏ.

Dữ liệu vào:

+ Chứa 2 số nguyên \(n,\ k\ (2 \leq k \leq n \leq 1000)\) nằm trên 1 dòng cách nhau bởi kí tự trắng.

Kết quả:

+ Một số nguyên dương là kết quả tìm được theo yêu cầu bài toán. (Kết quả chia lấy phần dư cho \(10^{9}\ + \ 7\)).

Ví dụ:

Giải thích ví dụ:

Quy ước: 0, 1 tương ứng với màu: đỏ, xanh

Dãy 3 bóng đèn có tất cả 3 dãy trạng thái khác nhau có đúng 2 bóng màu đỏ : 001, 100, 010

Ràng buộc dữ liệu:

+ \(50\%\) tests ứng với \(\ 1 \leq n \leq 30;\)

+ 50% tests \(1 \leq n \leq 1000\)