Đếm Đoạn

Một chuỗi được gọi là chuỗi nhị phân nếu nó chỉ bao gồm các ký tự 0 và 1.

Một đoạn con của chuỗi $s$ là một phần liên tiếp không rỗng thu được bằng cách lấy các ký tự từ một vị trí bắt đầu đến một vị trí kết thúc trong $s$. Hai đoạn con được coi là khác nhau nếu vị trí bắt đầu hoặc vị trí kết thúc của chúng trong chuỗi $s$ khác nhau.

Cho số nguyên $k$ và chuỗi nhị phân $s$, hãy tính số lượng đoạn con của chuỗi $s$ chứa đúng $k$ ký tự 1.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $k$ ($0 ≤ k ≤ 10^6$).

Dòng thứ hai chứa một chuỗi nhị phân không rỗng $s$ ($1 ≤ |s| ≤ 10^6$).

Kết quả

In ra một số nguyên duy nhất là số lượng đoạn con của chuỗi $s$ chứa đúng $k$ ký tự 1.

Chấm điểm

Subtask 1 (30 points). $|s| ≤ 3000$

Subtask 2 (70 points). $0 ≤ k ≤ 10^6$

Ví dụ

Input

2
01010

Output

4

Ghi chú

Trong ví dụ mẫu, hai đoạn con thỏa mãn không chứa ký tự 1 nào là đoạn từ vị trí 1 đến 1 (ký tự 0) và đoạn từ vị trí 3 đến 3 (ký tự 0). Do đó có 2 đoạn con thỏa mãn.