C. Еще одна строковая задача
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Строка называется бинарной, если она состоит только из символов «0» и «1».

Строка v называется подстрокой строки w, если она имеет ненулевую длину, и ее можно прочитать, начиная с некоторой позиции, в строке w. Например, у строки «010» есть шесть подстрок: «0», «1», «0», «01», «10», «010». Две подстроки считаются различными, если их позиции вхождения различны. Другими словами, каждую подстроку нужно учитывать столько раз, сколько она встречается.

Дана бинарная строка s. Ваша задача — найти количество ее подстрок, содержащих ровно k единиц.

Входные данные

В первой строке записано единственное целое число k (0 ≤ k ≤ 106). Во второй строке записана непустая бинарная строка s. Длина s не превосходит 106 символов.

Выходные данные

Выведите одно целое число — количество подстрок данной строки, содержащих ровно k символов «1».

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Примеры
Входные данные
1
1010
Выходные данные
6
Входные данные
2
01010
Выходные данные
4
Входные данные
100
01010
Выходные данные
0
Примечание

В первом примере искомые подстроки: «1», «1», «10», «01», «10», «010».

Во втором примере искомые подстроки: «101», «0101», «1010», «01010».