Назовем бинарную строку \(s\) восхитительной, если она содержит по крайней мере \(1\) символ 1 и длина строки делится на количество 1 в ней. К примеру, 1, 1010, 111 являются восхитительными, но 0, 110, 01010 не являются.
Вам дана бинарная строка \(s\). Посчитайте количество ее восхитительных подстрок.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Выходные данные
Выведите единственное число — количество восхитительных подстрок \(s\).
Примечание
В первом примере, все подстроки \(s\) являются восхитительными.
Во втором примере, есть следующие восхитительные подстроки \(s\): 1 (\(2\) раза), 01 (\(2\) раза), 10 (\(2\) раза), 010 (\(2\) раза), 1010, 0101
В третьем примере, ни одна подстрока не является восхитительной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
111
|
6
|
|
2
|
01010
|
10
|
|
3
|
0000
|
0
|
|
4
|
1111100000
|
25
|