Hôm nay là ngày đầu tiên Đạo và Mộc Nhĩ hẹn hò. Đạo quyết định mua hoa tặng Mộc Nhĩ. Trong cửa hàng hoa có ~N~ bông hoa xếp theo hàng ngang, bông hoa thứ ~i~ từ trái sang có ~A_i~ cánh hoa. Để tiết kiệm thời gian, Đạo quyết định mua một dãy các bông hoa liên tiếp trong cửa hàng để tạo thành một bó hoa. Ngoài ra, để bó hoa không quá đơn điệu, Đạo muốn trong bó hoa có đúng ~K~ bông hoa có lẻ cánh hoa. Vì có quá nhiều cách chọn, Đạo đang rất phân vân không biết nên chọn như thế nào.

Bạn là một trong những nhân viên của cửa hàng, hãy giúp Đạo đếm số cách chọn bó hoa.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 99999)~.

• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ là ~A_i~ ~(1 \le A_i \le 9^9)~.

Kết quả

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Sample Input

4 2
1 3 2 3

Sample Output

3

Chấm điểm

• Subtask 1 (60% số test): ~N \le 999~.

• Subtask 2 (40% số test): Không có ràng buộc gì thêm.