Bài đang bị tạm khoá, time limit được set rất thấp

Một xâu nhị phân ~t~ được gọi là tuyệt vời nếu đồng thời thỏa mãn 2 điều kiện sau đây:

• Tồn tại ít nhất một ký tự 1 trong xâu

• Độ dài của xâu ~t~ chia hết cho số lượng ký tự 1 trong xâu. Ví dụ: 1, 1010, 111 đều là các xâu tuyệt vời; còn 0, 110, 01010 thì không.

Cho xâu nhị phân ~s~, đếm số lượng xâu con của ~s~ là xâu tuyệt vời.

Xâu ~a~ được gọi là xâu con của xâu ~b~ khi xóa đi một vài ký tự (có thể là ~0~) ở đầu và một vài ký tự (có thể là ~0~) ở cuối xâu ~b~ thì có được xâu ~a~.

Input

Gồm một dòng duy nhất chứa xâu nhị phân ~s~ (~1\leq |s|\leq 100\ 000~) chỉ bao gồm các ký tự 0 và 1.

Output

Gồm một dòng duy nhất chứa số nguyên dương là số xâu con tuyệt vời của ~s~.

Sample Input 1

111

Sample Output 1

6

Sample Input 2

01010

Sample Output 2

10

Sample Input 3

0000

Sample Output 3

0

Sample Input 4

1111100000

Sample Output 4

25

Notes

Trong ví dụ đầu tiên, tất cả xâu con của ~s~ đều tuyệt vời.

Trong ví dụ thứ hai, các xâu con tuyệt vời của ~s~ là: 1 (~2~ lần), 01 (~2~ lần), 10 (~2~ lần), 010 (~2~ lần), 1010, 0101.

Trong ví dụ thứ ba, không có xâu con nào tuyệt vời.