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≤k≤10^6)~.
• Dòng 2: chứa một xâu nhị phân có độ dài ~≤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≤k≤len(s)≤500~.
• Subtask 2 (30% số điểm): ~1000≤k≤len(s)≤10000~.
• Subtask 3 (30% số điểm): ~10^5 ≤k≤len(s)≤10^6.~

Example

Input

2
01010 

Output

4