Cho một xâu nhị phân \(S\) (xâu chỉ gồm hai kí tự ‘0’ và ‘1’), xâu được bắt đầu từ vị trí \(1\). Gọi \(S\lbrack l,\ r\rbrack\) là một xâu con của xâu S gồm các kí tự liên tiếp của xâu S bắt đầu từ vị trí \(l\) đến vị trí \(r\ (1 \leq l \leq r \leq n).\) Gọi \(cnt\lbrack l,\ r\rbrack\) là số kí tự “1” của xâu con \(S\lbrack l,\ r\rbrack.\)

Yêu cầu: Đếm số xâu con \(S\lbrack l,\ r\rbrack\) của xâu \(S\) thỏa mãn \(r - l + 1\) chia hết cho \(cnt\lbrack l,\ r\rbrack.\)

Dữ liệu vào:

• Gồm một dòng ghi xâu \(S\) có độ dài \(n\ \left( 1 \leq n \leq 10^{5} \right).\)

Kết quả:

• Số lượng xâu con thỏa mãn yêu cầu của bài toán

Ví dụ:

Ràng buộc:

• Ràng buộc 1: có \(10\%\) số test tương ứng với \(10\%\) số điểm của bài có \(n \leq 1000;\)

• Ràng buộc 2: có \(20\%\) số test tương ứng với \(20\%\) số điểm của bài thỏa mãn xâu không có hai kí tự \("0"\) liên tiếp;

• Ràng buộc 3: có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn số kí tự “1” nhỏ hơn hoặc bằng \(300;\)

• Ràng buộc 4: có \(40\%\) số test tương ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.