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".