Đề bài

Dọc theo khu vườn nhà Tí có \(n\) chùm bóng đèn được đánh số từ \(1\) đến \(n\).
Chùm bóng đèn thứ \(i\) có số lượng bóng là \(a_i\).

Để chuẩn bị cho buổi tiệc sinh nhật, Tí muốn chọn một dãy liên tiếp các chùm đèn để trang trí khu vực chụp hình.
Ngoài ra, để khu vực này trở nên sinh động, Tí có một yêu cầu đặc biệt:
- Dãy các chùm đèn được chọn phải có đúng \(k\) chùm đèn chứa số lượng bóng là số lẻ.

Tí đang rất phân vân không biết có bao nhiêu cách chọn các chùm đèn thỏa mãn điều kiện trên.
Hãy giúp Tí đếm số cách chọn dãy chùm đèn hợp lệ.

Dữ liệu vào

• Tệp CHUMDEN.INP gồm:
• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \leq k \leq n \leq 10^6\)) là số lượng chùm đèn và số lượng chùm đèn có số bóng lẻ cần có trong dãy được chọn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^6\)) là số lượng bóng trong mỗi chùm đèn.

Dữ liệu ra

• Ghi ra tệp CHUMDEN.OUT một số nguyên duy nhất là số cách chọn dãy chùm đèn thỏa mãn yêu cầu.

Ràng buộc

• 30% số test có \(1 \leq n \leq 100\).
• 30% số test có \(100 < n \leq 5000\).
• 40% số test không có ràng buộc gì thêm.

Sample Input 1

4 2
1 3 2 3

Sample Output 1

3

Giải thích

Ta có \(n = 4\), \(k = 2\) và dãy số \([1, 3, 2, 3]\).
Ta cần tìm các dãy con liên tiếp có đúng 2 chùm đèn có số bóng là số lẻ.

Các dãy con hợp lệ là: 1. (1, 2) → \([1, 3]\) (có 2 số lẻ) 2. (1, 3) → \([1, 3, 2]\) (có 2 số lẻ) 3. (2, 4) → \([3, 2, 3]\) (có 2 số lẻ)

Vậy có 3 cách chọn thỏa mãn yêu cầu. ```