739. Three Pieces With the Same Number of Ones

Cut a binary string into THREE non empty contiguous pieces so that each piece holds the same number of 1 characters. Print how many ways there are, modulo 1000000007.

Two ways are different when the cut positions differ, even if the pieces read the same.

10101 -> 4 1001 -> 0 0000 -> 3 100100010100110 -> 12

## Two cases, and the second is not a detail

If the total number of ones is not divisible by 3, the answer is 0. Nothing can balance.

If there are NO ones at all, every piece trivially holds zero ones, so any two cut points work and the answer is the number of ways to choose them:

(n-1) choose 2 = (n-1)(n-2) / 2

This case has a completely different formula from the main one and is easy to forget, because the main method divides by the number of ones per piece. 0000 answering 3 is the check.

## Otherwise, the cuts are free within two gaps

Let each piece need m ones. Walk the positions of the ones. The first cut must fall AFTER the m-th one and AT OR BEFORE the (m+1)-th, so it may sit anywhere in the run of zeros between them. If those two ones are at positions p and q, there are q - p legal places.

The same holds for the second cut, between the 2m-th and (2m+1)-th one.

The two choices are independent, so the answer is the product of the two gaps.

Realising that the cut positions are constrained only by the GAP between two consecutive ones, and that everything between them is equally valid, is the whole problem. Counting the gaps rather than enumerating the cuts is what makes it linear.

## Why it is a product and not a sum

Any first cut combines with any second cut, because the first lies entirely left of the second by construction. Independent choices multiply.

## Where the off-by-one lives

The ones are 0-indexed, so the m-th one is ones[m-1] and the (m+1)-th is ones[m]. The first gap is ones[m] - ones[m-1] and the second is ones[2m] - ones[2m-1].

Using ones[m+1] or subtracting 1 from the gap are the two ways this goes wrong, and 111 answering 1 is the smallest case that catches both: both gaps are exactly 1.

## Overflow

A single gap can be almost the whole string: with ones at positions 0, 199998 and 199999 the first gap is 199998. What bounds the PRODUCT is that the two gaps span disjoint stretches, so they sum to at most n - 1 = 199999 and the product peaks when they are equal, at 99999 * 100000 = 9999900000, just under 10^10. So multiply in 64 bits and take the remainder afterwards.

The all-zeros formula is larger still: at n = 200000 it is 199999 * 199998 / 2 = 19999700001, about 2 * 10^10, so that branch needs 64 bits too.

## Cost

Time O(n). Space O(n) for the positions, or O(1) if the gaps are tracked on the fly.

Constraints - `1 ≤ length ≤ 200000` - every character is `0` or `1`