#P1270F. Awesome Substrings

Awesome Substrings

Description

Let's call a binary string ss awesome, if it has at least 11 symbol 1 and length of the string is divisible by the number of 1 in it. In particular, 1, 1010, 111 are awesome, but 0, 110, 01010 aren't.

You are given a binary string ss. Count the number of its awesome substrings.

A string aa is a substring of a string bb if aa can be obtained from bb by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

The first line contains the string ss (1s2000001 \leq |s|\le 200\,000) consisting only of zeros and ones.

Output a single number — the number of awesome substrings of ss.

Input

The first line contains the string ss (1s2000001 \leq |s|\le 200\,000) consisting only of zeros and ones.

Output

Output a single number — the number of awesome substrings of ss.

Samples

样例输入 1

111

样例输出 1

6

样例输入 2

01010

样例输出 2

10

样例输入 3

0000

样例输出 3

0

样例输入 4

1111100000

样例输出 4

25

Note

In the first sample, all substrings of ss are awesome.

In the second sample, we have the following awesome substrings of ss: 1 (22 times), 01 (22 times), 10 (22 times), 010 (22 times), 1010, 0101

In the third sample, no substring is awesome.