F. Восхитительные подстроки
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем бинарную строку $$$s$$$ восхитительной, если она содержит по крайней мере $$$1$$$ символ 1 и длина строки делится на количество 1 в ней. К примеру, 1, 1010, 111 являются восхитительными, но 0, 110, 01010 не являются.

Вам дана бинарная строка $$$s$$$. Посчитайте количество ее восхитительных подстрок.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

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

Первая строка содержит строку $$$s$$$ ($$$1 \leq |s|\le 200\,000$$$), состоящую только из нулей и единиц.

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

Выведите единственное число — количество восхитительных подстрок $$$s$$$.

Примеры
Входные данные
111
Выходные данные
6
Входные данные
01010
Выходные данные
10
Входные данные
0000
Выходные данные
0
Входные данные
1111100000
Выходные данные
25
Примечание

В первом примере, все подстроки $$$s$$$ являются восхитительными.

Во втором примере, есть следующие восхитительные подстроки $$$s$$$: 1 ($$$2$$$ раза), 01 ($$$2$$$ раза), 10 ($$$2$$$ раза), 010 ($$$2$$$ раза), 1010, 0101

В третьем примере, ни одна подстрока не является восхитительной.