UOJ Logo

NOI.AC

1S 512MB

#1665. Gakkipan的01串

统计

题目描述

Gakkipan最近沉迷数学无法自拔,虽然数学很好,但是对于字符串相关的计数问题却不是很擅长,现在他拥有一个01串,他想知道
对于所有的连续子串,包含恰好k个1的连续子串有多少个

文件输入

第一行一个数 k
第二行给出一个01串

文件输出

输出包含k个1的子串数量

输入样例

2
01010

输出样例

4

样例解释

4个子串分别为 101、0101、1010、01010

数据规模

对于所有的数据,0 <= k <= 1000000
对于20%的数据,串长 <= 1000
对于60%的数据,串长 <= 1000000
对于100%的数据,串长 <= 10000000