Строка называется бинарной, если она состоит только из символов «0» и «1».
Строка v называется подстрокой строки w, если она имеет ненулевую длину, и ее можно прочитать, начиная с некоторой позиции, в строке w. Например, у строки «010» есть шесть подстрок: «0», «1», «0», «01», «10», «010». Две подстроки считаются различными, если их позиции вхождения различны. Другими словами, каждую подстроку нужно учитывать столько раз, сколько она встречается.
Дана бинарная строка s. Ваша задача — найти количество ее подстрок, содержащих ровно k единиц.
Выходные данные
Выведите одно целое число — количество подстрок данной строки, содержащих ровно k символов «1».
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
Примечание
В первом примере искомые подстроки: «1», «1», «10», «01», «10», «010».
Во втором примере искомые подстроки: «101», «0101», «1010», «01010».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
1010
|
6
|
|
2
|
2
01010
|
4
|
|
3
|
100
01010
|
0
|