<p>You are given an array of <strong>positive</strong> integers <code>nums</code> of length <code>n</code>.</p>

<p>We call a pair of <strong>non-negative</strong> integer arrays <code>(arr1, arr2)</code> <strong>monotonic</strong> if:</p>

<ul>
	<li>The lengths of both arrays are <code>n</code>.</li>
	<li><code>arr1</code> is monotonically <strong>non-decreasing</strong>, in other words, <code>arr1[0] &lt;= arr1[1] &lt;= ... &lt;= arr1[n - 1]</code>.</li>
	<li><code>arr2</code> is monotonically <strong>non-increasing</strong>, in other words, <code>arr2[0] &gt;= arr2[1] &gt;= ... &gt;= arr2[n - 1]</code>.</li>
	<li><code>arr1[i] + arr2[i] == nums[i]</code> for all <code>0 &lt;= i &lt;= n - 1</code>.</li>
</ul>

<p>Return the count of <strong>monotonic</strong> pairs.</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">nums = [2,3,2]</span></p>

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

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

<p>The good pairs are:</p>

<ol>
	<li><code>([0, 1, 1], [2, 2, 1])</code></li>
	<li><code>([0, 1, 2], [2, 2, 0])</code></li>
	<li><code>([0, 2, 2], [2, 1, 0])</code></li>
	<li><code>([1, 2, 2], [1, 1, 0])</code></li>
</ol>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [5,5,5,5]</span></p>

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

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

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 2000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 50</code></li>
</ul>

"""

[2,3,2]
left = [0, 1, ]
right = [2, 2, ]

reduced the problem to:
find left and right element if target is x, and we have minLeft, and maxRight


def leftRightGen(target, minLeft, maxRight): # O(M), with M: nums[i], actual loop M//2
    # leftRightGen(2, 1, 2):
    l, r = minLeft, maxRight
    pairs = []
    while l <= target and r >= 0:
        if l + r < target: l += 1
        elif l + r > target: r -= 1
        else:
            pairs.append((l, r))
            l += 1
            r -= 1
    return pairs

# leftRightGen(2, 0, 2):

steps:
- for target in nums, find pairs based on previous pairs,
    - for every pairs, => can be reduced to DFS, each node is target with minLeft and maxRight
    - 

DFS, each node is target with minLeft and maxRight => return the number of goodPairs
if failed, no need to continue.
dfs(2, None, None):
  dfs(3, 0, 2):
    dfs(2, 1, 2):
      return 2 # last pairs: (1, 1) (2, 0)
    dfs(2, 2, 1)
      return 1 # last pairs: (2, 0)
  dfs(3, 1, 1)
    dfs(2, 2, 1)
      return 1 # last pairs: (2, 0)
    
    
"""
class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        cache = dict()
        def possiblePairs(target, minLeft, maxRight):
            if (target, minLeft, maxRight) in cache:
                return cache[(target, minLeft, maxRight)]
            l, r = minLeft, maxRight
            pairs = []
            while l <= target and r >= 0:
                if l + r < target: l += 1
                elif l + r > target: r -= 1
                else:
                    pairs.append((l, r))
                    l += 1
                    r -= 1
            cache[(target, minLeft, maxRight)] = pairs
            return pairs
        
        n = len(nums)
        dp = dict()
        def dfs(i, minLeft, maxRight):
            if i >= n: return 0 # ??? may be not used
            if (i, minLeft, maxRight) in dp:
                return dp[(i, minLeft, maxRight)]

            pairs = possiblePairs(nums[i], minLeft, maxRight)
            if i == n - 1:
                return len(pairs)

            total = 0
            for pair in pairs:
                total += dfs(i + 1, pair[0], pair[1])
            dp[(i, minLeft, maxRight)] = total
            return total
        
        MOD = 10**9 + 7
        ans = dfs(0, 0, nums[0])
        return (ans) % MOD

60784