如果一个二进制字符串 $$$s$$$ 至少有 $$$1$$$ 符号 1 并且字符串的长度可以被其中 1 的个数整除,那么我们称它为“awesome”。特别是,1、1010、111 很棒,但 0、110、01010 则不然。
给你一个二进制字符串$$$s$$$。计算它的精彩子串的数量。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
第一行包含字符串 $$$s$$$ ($$$1 \leq |s|\le 200\,000$$$) 仅由零和一组成。
输出
输出一个数字——$$$s$$$ 的令人敬畏的子字符串的数量。
示例
输入 #1
111
输出 #1
6
输入 #2
01010
输出 #2
10
输入 #3
0000
输出 #3
0
输入#4
1111100000
输出#4
25
注意
在第一个示例中,$$$s$$$ 的所有子字符串都很棒。
在第二个示例中,我们有以下很棒的 $$$s$$$ 子字符串:1($$$2$$$ 次)、01($$$2$$$ 次)、10($$$2$$$ 次)、010($$$2$$$ 次)、1010、0101
在第三个示例中,没有子字符串是很棒的。