如果字符串仅由字符“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”。