<p>Given the integers <code>zero</code>, <code>one</code>, <code>low</code>, and <code>high</code>, we can construct a string by starting with an empty string, and then at each step perform either of the following:</p>

<ul>
	<li>Append the character <code>&#39;0&#39;</code> <code>zero</code> times.</li>
	<li>Append the character <code>&#39;1&#39;</code> <code>one</code> times.</li>
</ul>

<p>This can be performed any number of times.</p>

<p>A <strong>good</strong> string is a string constructed by the above process having a <strong>length</strong> between <code>low</code> and <code>high</code> (<strong>inclusive</strong>).</p>

<p>Return <em>the number of <strong>different</strong> good strings that can be constructed satisfying these properties.</em> Since the answer can be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> low = 3, high = 3, zero = 1, one = 1
<strong>Output:</strong> 8
<strong>Explanation:</strong> 
One possible valid good string is &quot;011&quot;. 
It can be constructed as follows: &quot;&quot; -&gt; &quot;0&quot; -&gt; &quot;01&quot; -&gt; &quot;011&quot;. 
All binary strings from &quot;000&quot; to &quot;111&quot; are good strings in this example.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> low = 2, high = 3, zero = 1, one = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The good strings are &quot;00&quot;, &quot;11&quot;, &quot;000&quot;, &quot;110&quot;, and &quot;011&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= low&nbsp;&lt;= high&nbsp;&lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= zero, one &lt;= low</code></li>
</ul>

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        """
        from to high inclusive for i in range(low,high+1):

        zero = 1, one = 1

        # of good strings of length n

        say we know # of good strings of length n-1
        string either ends with zero zero's or one one's

        if i-zero <= 0:
            #not possible to take, so the number of good strings at least for this is
            0 
        
        opt[i] = max(1 + opt[i-zero],1 + opt[i-one])
        base cases:
        opt[0] = 0

        0 - 0
        1 - 1
        2 - 2
        3 - 2 + 1 =5 


        BF -- start at beginning, two chocies:
        get all possible strings below length high+1, then count 
        the number of good ones

        How can i get unique -> 

        you take "1" first OR take "0" first, then all others in this tree
        will be unique

        at this stage, with n number of chars left, assuming i take "1" first, what's
        the number of ways to build good strings?

        opt[i] -- i can be reached in many different ways, so you can get dups?

        0, 0 
        11, 
        go backward ->
        this represents your choice
        opt[i] = 1 + max(opt[i-zero],opt[i-one])
        """
        opt = {}
        opt[0] = 0

        opt[zero] = 1

        if one in opt:
            opt[one] += 1
        else:
            opt[one] = 1

        #what should be the base case?
        for i in range(1,high+1): 
            if i-zero < 0:
                take_zero = 0
            else:
                take_zero = opt[i-zero]
            
            if i-one < 0:
                take_one = 0
            else:
                take_one = opt[i-one]

            if i in opt:
                opt[i] += take_zero + take_one #have two options
            else:
                opt[i] = take_zero + take_one

        accum = 0
        for i in range(low,high+1):
            accum += opt[i]

        return accum % (10**9 + 7)

        
563