349. Another Problem on Strings



A binary string consists only of the characters "0" and "1". String v is a substring of string w if it has a non-zero length and can be read starting from any position in string w. For example, the string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. Therefore, if a string occurs multiple times, we should count it as the number of times it occurs. Given a binary string s, your task is to determine the number of substrings that contain exactly k characters "1".

Input Format

The first line contains an integer k. The second line contains a non-empty binary string s.

Output Format

Print a single number, which represents the number of substrings in the given string that contain exactly k characters "1".



1 1010




0 ≤ k ≤ 10^6 The length of s is at most 10^6 characters. Please avoid using the %lld specifier for 64-bit integers in C++. It is recommended to use the cin, cout streams or the %I64d specifier.

View Submissions