CF165C.Another Problem on Strings

A string is binary, if it consists only of 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 some position in string w. For example, string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. So, if some string occurs multiple times, we should consider it the number of times it occurs.

You are given a binary string s. Your task is to find the number of its substrings, containing exactly k characters "1".

如果一个字符串仅由字符“0”和“1”组成，则称其为二进制字符串。

若字符串 $v$ 具有非零长度，且可从字符串 $w$ 的某个位置开始连续读出，则称 $v$ 是 $w$ 的一个子串。例如，字符串 "010" 有六个子串："0"、"1"、"0"、"01"、"10"、"010"。若两个子串在原字符串中出现的位置不同，则认为它们是不同的子串。因此，若某个子串在原字符串中多次出现，应将其出现次数全部计入。

给定一个二进制字符串 $s$，你的任务是求出其中恰好包含 $k$ 个字符 "1" 的子串的个数。

The first line contains the single integer k (0 ≤ k ≤ 106). The second line contains a non-empty binary string s. The length of s does not exceed 106 characters.

第一行包含一个整数 $k$（$0 \leq k \leq 10^6$）。第二行包含一个非空的二进制字符串 $s$。字符串 $s$ 的长度不超过 $10^6$ 个字符。

Print the single number — the number of substrings of the given string, containing exactly k characters "1".

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——即给定字符串中恰好包含 k 个字符 "1" 的子串个数。

在 C++ 中，请勿使用 %lld 说明符读写 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first sample the sought substrings are: "1", "1", "10", "01", "10", "010".

In the second sample the sought substrings are: "101", "0101", "1010", "01010".

在第一个样例中，所求的子字符串为：“1”、“1”、“10”、“01”、“10”、“010”。

在第二个样例中，所求的子字符串为：“101”、“0101”、“1010”、“01010”。