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\).

Yêu cầu: 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

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

Output

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

Scoring

• \(len(s)\) là độ dài xâu nhị phân.
• Subtask \(1\) (\(40\%\) số điểm): \(1 \leq k \leq len(s) \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(1000 \leq k \leq len(s) \leq 10000\).
• Subtask \(3\) (\(30\%\) số điểm): \(10^5 \leq k \leq len(s) \leq 10^6\).

Example

2
01010 

4