Dọc theo con đường dẫn vào nhà ông bà BiBo được trang trí bởi ~n~ chậu hoa, mỗi chậu hoa trồng một loại hoa khác nhau. Chậu hoa thứ ~i~ có ~a_i~ bông hoa. BiBo quyết định chọn một dãy các chậu hoa liên tiếp dọc theo lối đi để bố trí khu vực chụp ảnh cho khách đến chơi nhà.

Để khu vực chụp ảnh không quá đơn điệu, BiBo muốn dãy các chậu hoa được chọn có đúng ~k~ chậu hoa có số bông hoa là số lẻ. Vì có quá nhiều cách chọn, BiBo đang phân vân không biết chọn như thế nào.

Yêu cầu: Em hãy giúp BiBo đếm số cách chọn dãy các chậu hoa thoả mãn điều kiện đưa ra.

Input

• Dòng 1: Hai số nguyên ~n, k~ ~(0 \le k \le n \le 3 \times 10^5)~;

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Output

In ra một số nguyên duy nhất thỏa mãn yêu cầu bài toán.

Scoring

Sample Input 1

4 2
1 3 2 3

Sample Output 1

3

Notes

Có ~3~ cách chọn thoả mãn ở các vị trí bắt đầu và kết thúc là ~(1,2)~, ~(1,3)~ và ~(2,4)~.