← 返回题目列表

Codeforces · 165/C

C. 弦乐的另一个问题

中文机器翻译题面 查看原题

如果字符串仅由字符“0”和“1”组成,则该字符串是二进制的。

如果字符串 v 具有非零长度并且可以从字符串 w 中的某个位置开始读取,则它是字符串 w 的子字符串。例如,字符串“010”有六个子字符串:“0”、“1”、“0”、“01”、“10”、“010”。如果两个子串出现的位置不同,则认为它们不同。因此,如果某个字符串出现多次,我们应该考虑它出现的次数。

给你一个二进制字符串 s。你的任务是找到它的子串的数量,恰好包含 k 个字符“1”。

输入

第一行包含单个整数 k (0 ≤ k ≤ 106)。第二行包含一个非空二进制字符串 s。 s 的长度不超过 106 个字符。

输出

打印单个数字 — 给定字符串的子字符串数,恰好包含 k 个字符“1”。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

1
1010

输出 #1

6

输入 #2

2
01010

输出 #2

4

输入 #3

100
01010

输出 #3

0

注意

在第一个示例中,查找的子字符串为:“1”、“1”、“10”、“01”、“10”、“010”。

在第二个示例中,查找的子字符串是:“101”、“0101”、“1010”、“01010”。