Count Ways to Build Good Strings

Start with an empty string. Each step appends either a block of zero zero characters or a block of one one characters. You may take any number of steps. Count the distinct resulting strings whose lengths are between low and high, inclusive, and return the count modulo 1000000007. Different strings count separately even when they have the same length.

Example 1:

Input: low = 2
high = 2
zero = 1
one = 1

Output: 4

Explanation: The four strings of length 2 are 00, 01, 10, and 11. Each can be built one character at a time.

Example 2:

Input: low = 3
high = 4
zero = 2
one = 2

Output: 4

Explanation: Both available blocks have length 2, so length 3 cannot be reached. At length 4, the strings are 0000, 0011, 1100, and 1111, giving four good strings.

Example 3:

Input: low = 2
high = 2
zero = 2
one = 1

Output: 2

Explanation: Append the zero block once to obtain 00, or append the one block twice to obtain 11. These are the only strings of length 2, so return 2.

Constraints:

• 1 <= low <= high <= 100000
• 1 <= zero, one <= low