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: Từ tệp văn bản SUBSTR. INP có cầu trúc:

• 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 không quá ~10^6~.

Kết quả: Ghi ra tệp văn bản SUBSTR.OUT gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc:

• Có 60% test ứng 60% số điểm của bài với K ≤ 100 và độ dài của xâu không quá 100;

• Có 20% test ứng 20% số điểm của bài với K ≤ 254 và độ dài của xâu không quá 254;

• Có 20% test khác ứng với 20% số điểm còn lại của bài với ~K ≤ 10^6~ và độ dài của xâu không quá ~10^6~.

Input 01:

2
01010

Output 01:

4

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

Input 02:

3
1111

Output 02:

2