349. Another Problem on Strings

0

Medium

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

Example

Input

1
1010

Output

6

Constraints

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.

Loading...

View Submissions

Console