Xét xâu ~S~ chỉ gồm các kí tự 0,1,?. Trong đó, các kí tự ? có thể được thay thế bằng 0 hoặc 1.

Gọi ~f(T,k)~ là số lượng xâu con liên tiếp độ dài ~k~ của xâu ~T~ sao cho xâu con này chứa toàn bộ kí tự ~1~.

Nhập vào xâu ~S~ và giá trị ~k~. Tính ~\sum f(S,k)~ với mọi xâu ~S~ có thể tạo ra. Dễ thấy có ~2^{cntQ}~ xâu ~S~ có thể có, với ~cntQ~ là số kí tự ? trong xâu ~S~.

Input

• Dòng thứ nhất chứa 2 số nguyên ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~ - tương ứng với độ dài xâu ~S~ và hằng số ~k~.

• Dòng thứ hai nhập vào xâu ~S~ gồm kí tự 0,1,?.

Output

• In ra kết quả cần tìm. Vì kết quả có thể rất lớn, hãy in ra số dư sau khi chia cho ~10^9 + 9~.

Scoring

• Subtask ~1~ (~30~ điểm): ~n \le 1000~.

• Subtask ~2~ (~30~ điểm): ~cntQ \le 20~.

• Subtask ~3~ (~40~ điểm): không có ràng buộc gì thêm.

Sample Input 1

3 1
?01

Sample Output 1

3

Notes

• ~f(~001~, 1) = 1~

• ~f(~101~, 1) = 2~