<p>You are given 3 positive integers <code>zero</code>, <code>one</code>, and <code>limit</code>.</p>

<p>A <span data-keyword="binary-array">binary array</span> <code>arr</code> is called <strong>stable</strong> if:</p>

<ul>
	<li>The number of occurrences of 0 in <code>arr</code> is <strong>exactly </strong><code>zero</code>.</li>
	<li>The number of occurrences of 1 in <code>arr</code> is <strong>exactly</strong> <code>one</code>.</li>
	<li>Each <span data-keyword="subarray-nonempty">subarray</span> of <code>arr</code> with a size greater than <code>limit</code> must contain <strong>both </strong>0 and 1.</li>
</ul>

<p>Return the <em>total</em> number of <strong>stable</strong> binary arrays.</p>

<p>Since the answer may be very 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>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">zero = 1, one = 1, limit = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The two possible stable binary arrays are <code>[1,0]</code> and <code>[0,1]</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">zero = 1, one = 2, limit = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p>The only possible stable binary array is <code>[1,0,1]</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">zero = 3, one = 3, limit = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">14</span></p>

<p><strong>Explanation:</strong></p>

<p>All the possible stable binary arrays are <code>[0,0,1,0,1,1]</code>, <code>[0,0,1,1,0,1]</code>, <code>[0,1,0,0,1,1]</code>, <code>[0,1,0,1,0,1]</code>, <code>[0,1,0,1,1,0]</code>, <code>[0,1,1,0,0,1]</code>, <code>[0,1,1,0,1,0]</code>, <code>[1,0,0,1,0,1]</code>, <code>[1,0,0,1,1,0]</code>, <code>[1,0,1,0,0,1]</code>, <code>[1,0,1,0,1,0]</code>, <code>[1,0,1,1,0,0]</code>, <code>[1,1,0,0,1,0]</code>, and <code>[1,1,0,1,0,0]</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= zero, one, limit &lt;= 1000</code></li>
</ul>

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 +7

        # Initialize dp0 and dp1
        dp0 = [ [0]*(one +1) for _ in range(zero +1) ]
        dp1 = [ [0]*(one +1) for _ in range(zero +1) ]

        # Initialize prefix0 and prefix1
        prefix0 = [ [0]*(one +1) for _ in range(zero +1) ]
        prefix1 = [ [0]*(zero +1) for _ in range(one +1) ]

        # Set base cases for dp0
        for z in range(1, min(zero, limit) +1):
            dp0[z][0] =1

        # Set base cases for dp1
        for o in range(1, min(one, limit) +1):
            dp1[0][o] =1

        # Iterate through all possible z and o
        for z in range(zero +1):
            for o in range(one +1):
                if z >0:
                    # Calculate sum1 = sum of dp1[z -k][o] for k=1 to min(z, limit)
                    max_k = min(z, limit)
                    sum1 = prefix1[o][z -1] 
                    if z - limit -1 >=0:
                        sum1 = (sum1 - prefix1[o][z - limit -1]) % MOD
                    else:
                        sum1 = sum1 % MOD
                    dp0[z][o] = (dp0[z][o] + sum1) % MOD

                if o >0:
                    # Calculate sum0 = sum of dp0[z][o -k] for k=1 to min(o, limit)
                    max_k = min(o, limit)
                    sum0 = prefix0[z][o -1]
                    if o - limit -1 >=0:
                        sum0 = (sum0 - prefix0[z][o - limit -1]) % MOD
                    else:
                        sum0 = sum0 % MOD
                    dp1[z][o] = (dp1[z][o] + sum0) % MOD

                # Update prefix0
                if o ==0:
                    prefix0[z][o] = dp0[z][o] % MOD
                else:
                    prefix0[z][o] = (prefix0[z][o -1] + dp0[z][o]) % MOD

                # Update prefix1
                if z ==0:
                    prefix1[o][z] = dp1[z][o] % MOD
                else:
                    prefix1[o][z] = (prefix1[o][z -1] + dp1[z][o]) % MOD

        # The answer is the sum of sequences ending with 0 and 1
        return (dp0[zero][one] + dp1[zero][one]) % MOD

173700