Xâu con

Một xâu nhị phân là xâu chỉ gồm hai ký tự 0 và 1.
Xâu \(v\) được gọi là xâu con của \(w\) nếu \(v\) có độ dài \(\ge 1\) và là một đoạn liên tiếp trong \(w\). Hai xâu con ở các vị trí khác nhau được tính là khác nhau.

Cho một xâu nhị phân \(s\) và một số nguyên \(K\), hãy đếm xem có bao nhiêu xâu con của \(s\) chứa đúng \(K\) ký tự 1.

Input

• Dòng đầu chứa số nguyên \(K\) (\(0 \le K \le 10^6\)).

• Dòng thứ hai chứa xâu nhị phân \(s\) có độ dài \(n\), với \(1 \le n \le 10^6\).

Output

In ra một số nguyên duy nhất --- số lượng xâu con chứa đúng \(K\) ký tự 1.

Notes

Với \(K = 1\), $s = $ 1010: có \(6\) xâu con thỏa mãn.

Scoring

• Subtask 1 (30 điểm): \(n \le 1000\).

• Subtask 2 (70 điểm): \(n \le 10^6\).