Count good binary strings

Problem A binary string is "good" if 1s appear only in groups of exactly one_group (if at all) and 0s appear only in groups of exactly zero_group. Given min_length, max_length, one_group, zero_group, count the good binary strings with length in [min_length, max_length], modulo 10^9+7.

Input / Output

• Input: integers min_length, max_length, one_group, zero_group.
• Output: count of good strings, mod 1e9+7.

Constraints

• max_length up to 10^5 — O(max_length) DP expected.

Example

• min_length=1, max_length=3, one_group=2, zero_group=1 → 6: "0", "11", "00", "110", "011", "000".

Expected approach

• DP over lengths: dp[L] = number of good strings of exactly length L, with dp[0] = 1 and dp[L] = dp[L − one_group] + dp[L − zero_group] (append a full group of 1s or of 0s; groups of the same digit merging is impossible because each append is a whole allowed group — note when one_group == zero_group the two terms both apply). Answer = Σ dp[L] for L in [min_length, max_length], all mod 1e9+7. O(max_length) time and space.