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

Dữ liệu vào:

-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~

Dữ liệu ra:

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

Ví dụ

Input

2

01010

Output

4

Giải thích ví dụ:

có 4 xâu con chứa 2 ký tự 1 là: "101", "0101", "1010", "01010"

Ràng buộc:

gọi n là độ dài xâu

• Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.

• Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.

• Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 1.000.000.