Bài 3. Xâu con

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự “0” hoặc 1

Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.

Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng k ký tự “1”

INPUT: SUBSTR.INP

• Dòng 1 chứa một số nguyên k (0 ≤ k ≤ 10⁶)
• Dòng 2 chứa một xâu nhị phân có độ dài ≤ 10⁶

OUTPUT: SUBSTR.OUT

• Một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

* Giải thích: có 4 xâu chứa 2 ký tự 1 là: “101”, “0101”, “1010”, “01010”

* Chú ý:

• 40% test đầu tiên có 1 ≤ k ≤ độ dài xâu nhị phân ≤ 500
• 30% test tiếp theo có 1000 ≤ k ≤ độ dài xâu nhị phân ≤ 10000
• 30% test cuối cùng có 10⁵ ≤ k ≤ độ dài xâu nhị phân ≤ 10⁶