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’.

Dữ liệu vào:

+ Dòng 1 chứa một số nguyên \(k\).

+ Dòng 2 chứa một xâu nhị phân.

Kết quả: 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’

Giới hạn:

• 1 ≤ độ dài xâu nhị phân ≤ 10⁶.

• 0 ≤ k ≤ độ dài xâu nhị phân.

Ràng buộc:

• 40% số test ứng với 40% số điểm của bài toán có: 1 ≤ độ dài xâu nhị phân ≤ 5.10².

• 30% số test ứng với 30% số điểm của bài toán có: 5.10² ≤ độ dài xâu nhị phân ≤ 10⁵.

• 30% số test ứng với 30% số điểm của bài toán có: 10⁵ ≤ độ dài xâu nhị phân ≤ 10⁶.