<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;= 1000</code></li>
</ul>

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:

        max_n = max(nums)
        # Create a dp 2d array, 
        # with the rows representing the prev element in array1
        # and the cols representing the position of the nums array
        dp = [[0] * len(nums) for _ in range(max_n + 1)]

        for i in range(len(nums) - 1, -1, -1):
            for prev in range(max_n, -1, -1):

                # We always sum the value from dp[prev+1][i], 
                # so we need to calculate later only the new possibilities by having the current prev instead of prev+1
                val = dp[prev+1][i] if prev < max_n else 0

                # We start from the last col, dp[prev][i] can't be bigger than prev
                # And prev can't actually be the prev if it's bigger than nums[i-1]
                # So if the prev is invalid here (prev > nums[i-1]) we assign 0
                # If nums[i] < prev, we also assign 0 because there is no possible number to make arr1 motononic
                # If not, there is one new possibility, we assign 1 + the possibilities from dp[prev+1][i]
                if i == len(nums) - 1:
                    if prev <= nums[i] and prev <= nums[i-1]:
                        val += 1
                
                elif i == 0:
                    val += dp[prev][i+1]
                else:
                    p1 = prev
                    p2 = nums[i-1] - p1

                    if p2 >= 0:
                        x = max(p1, nums[i] - p2)
                        val += dp[x][i+1]

                dp[prev][i] = val
                    

        # for r in dp: print(r)

        return dp[0][0] % (10**9+7)
296922