Ở một kỳ thi Codeforces không gần đây, bạn Hesll một lần nữa lại đọc nhầm đề mà quên mất rằng, nó chỉ là bài B mà thôi. Hesll đọc nhầm đề bài thành như sau:

Với một xâu nhị phân \(X\) bất kỳ, gọi \(x\) và \(y\) lần lượt là số lượng chữ số \(1\) và \(0\) trong xâu nhị phân đó. Khi đó, trọng số \(w\) của xâu \(X\) là:

Cho xâu \(S\) có \(n = |S|\) là độ dài xâu. Một xâu được gọi là xâu con liên tiếp (gọi tắt là xâu con) của xâu \(S\) nếu nó có thể được tạo bằng cách xóa đi một số ký tự đầu tiên và cuối cùng của xâu. Khi đó, xâu con bắt đầu từ vị trí \(l\), kết thúc tại vị trí \(r\) được gọi là xâu \(S_{l, r}\) \((0 \le l \le r < n)\).

Ví dụ, abc là xâu con liên tiếp của dabce nhưng không phải là xâu con liên tiếp của adbce.

Cho xâu nhị phân \(S\) có độ dài \(n\). Tính \(\sum\limits_{l=0}^{n-1} \sum\limits_{r=l}^{n-1} w(S_{l,r})\), hay nói cách khác là tổng trọng số của mọi xâu con liên tiếp của \(S\).

Not-fun fact: Bài này được ra trong Round 6 LQDOJ CUP 2023.
Mình rất cay là tự nhiên mình bị ép đẩy \(n = 10^7\) để tránh thuật \(\mathcal{O}(n \log n)\), và vì vậy nên đầu vào phải ép về dạng base64.
Xong mình đòi code \(\mathcal{O}(n)\) thì đếch ai code cho mình cả.
Cuối cùng lúc đi thi thì rất nhiều bạn code lỗi phần base64.
Bài này là bài mình tâm đắc nhất, nhưng cuối cùng fail vl huhu.

Input

• Một dòng duy nhất chứa một xâu nhị phân có độ dài \(n \leq 10^5\), chỉ gồm các ký tự 0 và 1.

Output

• In ra đáp án của bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^5\), toàn bộ các ký tự của \(S\) đều giống nhau.
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 10^5\), tồn tại duy nhất một vị trí \(i\) sao cho \(S_i \neq S_{i + 1}\) (\(0 \le i < n-1\)).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

0110

18