Một nhóm sinh viên gồm \(n\) người tham gia một chuyến team-building do khoa tổ chức. Khi đến điểm du lịch, đoàn sinh viên được tham gia một số trò chơi vận động. Trong đó có một trò chơi như sau: Các sinh viên xếp thành một hàng ngang. Mỗi khi có tiếng còi, các sinh viên đứng cạnh nhau cần di chuyển xích lại gần sao cho hình thành một số nhóm thỏa mãn:

• Mỗi nhóm gồm các sinh viên đứng cạnh nhau theo thứ tự xếp hàng ban đầu
• Chênh lệch số nam và nữ trong mỗi nhóm không được vượt quá số \(k\) mà ban tổ chức cho.

Sau mỗi tiếng còi các sinh viên cần tạo ra cách ghép nhóm khác với tất cả các lượt trước đó. Do vậy, bạn hãy giúp đoàn sinh viên đếm xem có bao nhiêu cách ghép nhóm khác nhau thỏa mãn các yêu cầu trên.

Biết rằng hai cách ghép nhóm gọi là khác nhau khi hai sinh viên bất kì chung nhóm trong cách ghép này lại không chung nhóm trong cách ghép kia.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 5000)\) lần lượt là số lượng sinh viên trong đoàn và chênh lệch nam nữ tối đa của mỗi nhóm.
• Dòng tiếp theo chứa một xâu nhị phân độ dài \(n\) với kí tự 1 tượng trưng cho sinh viên nam, và 0 cho sinh viên nữ.

Output

• In ra một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 500\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 1
1011

5

10 2
1011010001 

472