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

'''
动态规划
示例 3，zero=3, one=3, limit=2。

先解释 limit，意思是数组中至多有连续 limit 个 0，且至多有连续 limit 个 1。

考虑稳定数组的最后一个位置填 0 还是 1：

填 0，问题变成剩下 2 个 0 和 3 个 1 怎么填。
填 1，问题变成剩下 3 个 0 和 2 个 1 怎么填。
这两个都是和原问题相似的子问题。
看上去，定义 dfs(i,j) 表示用 i 个 0 和 j 个 1 构造稳定数组的方案数？但这样定义不方便计算 limit 带来的影响。

改成定义 dfs(i,j,k) 表示用 i 个 0 和 j 个 1 构造稳定数组的方案数，其中第 i+j 个位置要填 k，其中 k 为 0 或 1。

如果 k=0，考虑第 i+j−1 个位置要填什么：

填 0，问题变成 dfs(i−1,j,0)。
填 1，问题变成 dfs(i−1,j,1)。
但是，dfs(i−1,j,0) 包含了「最后连续 limit 个位置填 0」的方案，如果在这个方案末尾再加一个 0，就有连续 limit+1 个 0 了，这是不合法的。

dfs(i−1,j,0) 中的「最后连续 limit 个位置填 0」的方案有多少个？

因为 dfs 的定义是稳定数组的方案数，只包含合法方案，所以在最后连续 limit 个位置填 0 的情况下，倒数第 limit+1 个位置一定要填 1，这有 dfs(i−limit−1,j,1) 种方案。对于 dfs(i,j,0) 来说，这 dfs(i−limit−1,j,1) 个方案就是不合法方案了，要减去，得

dfs(i,j,0)=dfs(i−1,j,0)+dfs(i−1,j,1)−dfs(i−limit−1,j,1)
同理得

dfs(i,j,1)=dfs(i,j−1,0)+dfs(i,j−1,1)−dfs(i,j−limit−1,0)
递归边界 1：如果 i<0 或者 j<0，返回 0。也可以在计算 dfs(i−limit−1,j,1) 前判断 i>limit，在计算 dfs(i,j−limit−1,0) 前判断 j>limit。

递归边界 2：如果 i=0，那么当 k=1 且 j≤limit 的情况下返回 1，否则返回 0；如果 j=0，那么当 k=0 且 i≤limit 的情况下返回 1，否则返回 0。

递归入口：dfs(zero,one,0)+dfs(zero,one,1)，即答案。


时间复杂度：O(zero⋅one)。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(zero⋅one)，单个状态的计算时间为 O(1)，所以动态规划的时间复杂度为 O(zero⋅one)。
空间复杂度：O(zero⋅one)。有多少个状态，memo 数组的大小就是多少。
'''
class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def dfs(i, j, k):
            if i == 0:
                return 1 if k == 1 and j <= limit else 0
            if j == 0:
                return 1 if k == 0 and i <= limit else 0
            if k == 0:
                return (dfs(i-1, j, 0) + dfs(i-1, j, 1) - (dfs(i-limit-1, j, 1) if i > limit else 0)) % MOD
            else:
                return (dfs(i, j-1, 0) + dfs(i, j-1, 1) - (dfs(i, j-limit-1, 0) if j > limit else 0)) % MOD
        ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD
        dfs.cache_clear()  # 防止爆内存
        return ans
375700