Let \(E(Z, S, H)\) be the maximum number of `*`s which can fit alongside \(Z\) `0`s, with \(S\) `*`s before the first `0`, in a BST of height at most \(H\) (only relevant for \(Z > 0\)). To compute this in \(O(1)\) time, we should arrange as many `*`s as possible as ancestors of the first `0` (\(\min(S, H-Z+1)\) of them). We can then compute the maximum total number of nodes in a BST of height \(H\) (\(2^{H+1} - 1\)), subtract the number of nodes in the first `0`'s subtree, and potentially add back the number of nodes in the first `0`'s right subtree (if it's possible to get any `*`s there.

Let \(F(P, Z, S)\) be the minimum BST height for \(P\) `*`s and \(Z\) `0`s, with \(S\) `*`s before the first `0` (again only relevant for \(Z > 0\)). This can be computed in \(O(log(P + Z))\) by simply binary searching for the minimum height and evaluating \(E(Z, S, H)\).

Finally, let \(G(P)\) be the minimum BST height for \(P\) `*`s and no `0`s. This can similarly be computed in \(O(log(P))\) using binary search or simple math.

Now, letting \(Z\) be the number of `0`s present in any given substring, we'll we'll separately consider 3 categories of \(Z\) values and add their results up.

**Category 1:** \(Z = 0\)

Let \(C_P\) be the number of substrings with \(P\) `*`s and no `0`s. We can compute \(C_{1..N}\) in \(O(N)\) time relatively simply, by iterating through the string and dividing it into intervals of consecutive `*`s (noting that an interval of \(P\) `*`s should increase `C_P` by 1, `C_{P-1}` by 2, and so on, with `C_1` increased by `P`).

After that, we only need to add up \(C_P * G(P)\) for each \(P\), taking \(O(N log(N))\) (or as little as \(O(N)\)) time.

**Category 2:** \(1 \le Z \le 20\)

The significance of the cutoff of \(20\) (\(\lceil log(N) \rceil\)) is explained in Category 3 below.

For now, for each such value of \(Z\), we can sweep through the string and find the \(O(N)\) possible intervals of `0`s which it could span. Each such interval may be described by the triple \((L, M, R)\), such that there are \(L\) `*`s just left of the leftmost `0`, \(M\) `*`s in total between the leftmost and rightmost `0`s, and \(R\) `*`s just right of the rightmost `0`.

For each interval, we'll consider each possible number \(S\) of `*`s left of the leftmost 0 to use (such that \(0 \le S \le L\)). Note that this amounts to \(O(N)\) \(S\) values considered across all intervals for any given \(Z\) value. For each \(S\), we need to include \(F(P, Z, S)\) for each \(P\) such that \(S+M \le P \le S+M+R\). This amounts to \(O(N^2)\) \((P, Z, S)\) triples in total, which is too many to individually consider. However, \(F(P, Z, S)\) for fixed values of \(Z\) and \(S\) is monotonic over \(P\) and only takes on \(O(log(N))\) distinct values (dictated by \(E(Z, S, H)\) for \(0 \le H \le \lceil log(N) \rceil\)). These computations can therefore be done in \(O(log(N))\) time for each \(S\). The total time complexity is then \(O(N log(N))\) for each value of \(Z\), and \(O(N log^2(N))\) across all of Category 2.

**Category 3:** \(Z > 20\)

For each such \(Z\), there are enough `0`s that the BST's height is entirely dictated by them, no matter how many `*`s there are. In particular, when \(Z > 20\), \(F(P, Z, S)\) equals \(Z-1\) if \(S = 0\), or otherwise equals \(Z\).

To arrive at the sum of these \(F\) evaluations across all strings with more than 20 `0`s, we'll independently count the "contribution" of each `0` in the string. We'll begin by adding on the total number of intervals containing it (easily computable in \(O(1)\) time), and then subtracting the number of intervals containing it which have no more than 20 `0`s (doable in \(O(log(N))\) time by considering each possible leftmost `0` in such intervals (of which there are at most 21 options). Finally, we'll subtract the number of intervals which begin with it and have more than 20 `0`s (to account for cases in which \(F(P, Z, S)\) equals \(Z-1\) rather than \(Z\)), which is also easily computable in \(O(1)\) time. In total, then, Category 3 can be handled in \(O(N log(N))\).

Putting all of the above together, the time complexity of this solution comes out to \(O(N log^2(N))\).