<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>, as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.</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>

<p>Note that the binary arrays <code>[1,1,0]</code> and <code>[0,1,1]</code> have subarrays of length 2 with identical elements, hence, they are not stable.</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;= 200</code></li>
</ul>

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        # An array on solutionts dp[count of ones][count of zeroes][ends with 0 or 1]
        dp = [[[0, 0] for _ in range(zero + 1)] for _ in range(one + 1)]

        # 1 empty dataset ends with either 0 or 1
        dp[0][0][0] = 1
        dp[0][0][1] = 1

        # 1 solution with only 1s exist or 0 if over the limit
        curZero = 0
        for curOne in range(1, one + 1):
            dp[curOne][curZero][1] = int(curOne <= limit)

        for curZero in range(1, zero + 1):
            curOne = 0
            # 1 solution with only 0s exist or 0 if over the limit
            dp[curOne][curZero][0] = int(curZero <= limit)

            for curOne in range(1, one + 1):
                # for every cell

                # try to insert the zeroes at the end, adding to the appropriate solutions ending with 1
                for tailZeros in range(1, min(limit, curZero) + 1):
                    dp[curOne][curZero][0] += dp[curOne][curZero - tailZeros][1]
                dp[curOne][curZero][0] %= 1000000007

                # try to insert the ones at the end, adding to the appropriate solutions ending with 0
                for tailOnes in range(1, min(limit, curOne) + 1):
                    dp[curOne][curZero][1] += dp[curOne - tailOnes][curZero][0]
                dp[curOne][curZero][1] %= 1000000007

        # Sum the last dp element, ending with 0 or with 1
        return sum(dp[one][zero]) % 1000000007
22300