<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:

    
       	//brute force->>using recurssion-TLE 

       	//     int mod=1e9+7;
       	
        //     int solve(int size,int zero,int one,int n){
       	//         if(size==n){
       	//             return 1;
       	//         }
       	//         if(size>n)return 0;

       	//         int res = 0;
       	//         res = res + solve(size + zero,zero,one,n)%mod;

       	//         res = res + solve(size + one,zero,one,n)%mod;

       	//         return res;
       	//      }

       	//     int countGoodStrings(int low, int high, int zero, int one) {
       	//         int ans=0;
       	//         for(int i=low;i<=high;i++){
       	//             ans=ans+solve(0,zero,one,i)%mod;
       	//         }

       	//      return ans;   
       	//     }
       	// };

    
    
    
    
       	// using dp--->

    int mod = 1e9 + 7;

    int solve(int target, vector<int> &dp, int one, int zero)
    {
        if (target == 0)
            return 1;
        if (target < 0)
            return 0;
        if (dp[target] != -1)
            return dp[target];
        
        long long sum;
        sum = solve(target - one, dp, one, zero) + solve(target - zero, dp, one, zero);
        return dp[target] = (sum % (mod));
    }
    
    
    
    int countGoodStrings(int low, int high, int zero, int one)
    {
        vector<int> dp(high + 1, -1);
        int ans = 0;

        for (int i = low; i <= high; i++)
        {
            ans = ((ans % mod) + (solve(i, dp, one, zero) % mod)) % mod;
        }
        return ans;
    }
};
14059