Dọc theo khu vườn nhà Tí được trang trí bởi ~n~ trùm bóng đèn ~a_1, a_2, ..., a_n~, chùm đèn thứ ~i~ có ~a_i~ bóng. Để chuẩn bị cho buổi tiệc sinh nhật của mình, Tí quyết định chọn một dãy các chùm đèn liên tiếp trong khu vường để bố trí khu vực chụp hình cho khác mời đến dự tiệc. Ngoài ra, để khu vực chụp hình không quá đơn điệu, Tí muốn dãy các chùm đèn được chọn có đúng ~k~ chùm đèn có số bóng là số lẻ. Vì có quá nhiều cách chọn, Tí đ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 người bạn thân của Tí, hãy giúp Tí đếm số cách chọn các chùm đèn trong khu vườn thỏa mãn yêu cầu Tí đặt ra.

Input

Đọc từ tệp văn bản CHUMDEN.INP

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~k(1 \le k \le n \le 10^6)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n(1 \le a_i \le 10^6)~ các số cách nhau một khoản trắng.

Output

Ghi ra tệp văn bản CHUMDEN.OUT một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

CHUMDEN.INP

4 2
1 3 2 3

CHUMDEN.OUT

3

Giải thích

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

Ràng buộc

• Có ~30~% số test đầu với ~1 \le n \le 100~
• Có ~30~% số test tiếp theo với ~100 < n \le 5.10^3~
• Có ~40~% số test còn lại không có ràng buộc gì thêm