Hôm nay là ngày đầu tiên Luna và Tina hẹn hò. Luna quyết định mua hoa tặng Tina. 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, Luna 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, Luna 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, Luna đ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 Luna đếm số cách chọn bó hoa.

Input

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

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

Output

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

Simple Input

4 2
1 3 2 3

Simple Output

3