<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 {
public:
int mod = 1000000007;
int bfs(int low, int high, int zero, int one){
    int ans = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int length = q.front();
        q.pop();
        if(length > high){
            continue;
        }
        if(length >= low and length <= high){
            ans = (ans+1)%mod;
        }
        q.push(length+zero);
        q.push(length+one);
    }
    return ans;
}

int dfs(int length, int low, int high, int zero, int one, vector<int>& dp){
    if(length > high){
        return 0;
    }
    if(dp[length] != -1){
        return dp[length];
    }
    int include = (length >= low and length <= high) ? 1 : 0;
    return dp[length] = (include + dfs(length + zero, low, high, zero, one, dp) + dfs(length + one, low, high, zero, one, dp)) % mod;
}
    int countGoodStrings(int low, int high, int zero, int one) {   
        vector<int> dp(high+1,-1);     
        return dfs(0,low,high,zero,one,dp);
    }
};
20303