O(N*(M + Log(M)) Solution with PrefixSum and Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \n    """\n    i = 2 (0, 2), (1, 1), (2, 0)\n    i = 1 (3, 0), (2, 1), (1, 2), (0, 3)\n  
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n    """\n    i = 2 (0, 2), (1, 1), (2, 0)\n    i = 1 (3, 0), (2, 1), (1, 2), (0, 3)\n    i = 0 (2, 0), (1, 1), (0, 2)\n    [0, 1, 2, 3]\n\n    i=1\n    [0, 1, 2, 3]\n    3, 0 look for 3 or higher (cancel)\n    0, 3 look for 0 or higher (0, 2), (1, 1), (2, 0) (+3)\n    1, 2 look for 1 or higher (1 1) (2, 0) (+2)\n    2, 1 look for 2 or higher (2 0) (+1)\n\n    i=0\n    0, 2 looks for 0 or higher (0, 3) + 0\n    0, 2 looks for 0 or higher (1, 2) + 2\n    0, 2 looks for 0 or higher (2, 1) + 1\n\n    1, 1 looks for 1 or higher (0, 3) False\n    1, 1 looks for 1 or higher (1, 2) False\n    1, 1 looks for 1 or higher (2, 1) +1\n\n    2, 0 looks for 2 or higher (0, 3) False\n    2, 0 looks for 1 or higher (1, 2) False\n    2, 0 looks for 1 or higher (2, 1) False\n    """\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse Prefix Sum and Binary Search to find the smallest arr1 element such that it satisfy this condition arr1 >= num1 and arr2 <= num2.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**O(N*M + NLog(M))** where **M** is the maximum number in the array\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**O(M)**\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        def findSmallest(num1, num2, n):\n            low, high = num1, n\n\n            while low <= high:\n                mid = (low + high) // 2\n                tmp2 = n - mid\n\n                if tmp2 <= num2:\n                    high = mid - 1\n                else:\n                    low = mid + 1\n\n            return low\n                \n        MOD = 10 ** 9 + 7\n        n = len(nums)\n        last = nums[-1]\n        dp = [1] * (last + 1)\n\n        for i in range(n - 2, -1, -1):\n            preSum = list(accumulate(dp, initial=0))\n            num, prev = nums[i], nums[i + 1]\n            tmp_dp = []\n            toLook = -1\n            for a1 in range(num + 1):\n                if a1 > prev:\n                    tmp_dp.extend([0] * (num - a1 + 1))\n                    continue\n\n                a2 = num - a1\n                if toLook >= 0:\n                    toLook += 1\n                else:\n                    toLook = findSmallest(a1, a2, prev)\n\n                toAdd = preSum[-1] - preSum[toLook]\n                tmp_dp.append(toAdd)\n\n            dp = tmp_dp\n\n        return sum(dp) % MOD\n```
['Binary Search', 'Dynamic Programming', 'Prefix Sum', 'Python3']