Chef Loves Beautiful Strings (Hard Version)

**This is the hard version of the problem. Here, you need to compute the sum of beauties over all substrings of the given binary string $S$.** The *beauty* of a **binary** string $T$, denoted $f(T)$, is defined as follows. Consider the following algorithm ($T$ is $1$-indexed). - Let $\text{score} = 0$. - Repeat the following $|T|-1$ times: - Choose an index $i$ ($1 \leq i \leq |T|$), delete