C++ O(N)
Intuition\n Dynamic programing + Prefix Sum \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity: O(1001 * nums.s
# Intuition\n<!-- Dynamic programing + Prefix Sum -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(1001 * nums.size());\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O (1001 * nums.size())\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        const long long mod = 1000000007;\n        vector<vector<int> > dp (nums.size(), vector<int>(1001, 0));\n        for (int i = nums.size() - 1; i >= 0; --i) \n            for (int a = 0; a < 1001; ++a) {\n                const long long x = a == 0 ? 0 : dp[i][a - 1];\n                if (a <= nums[i]) {\n                    if (i == nums.size() - 1) \n                        dp[i][a] = x + 1;\n                    else {\n                        const long long y = dp[i + 1][1000];\n                        const int threshold = nums[i + 1] > nums[i] ? nums[i + 1] - nums[i] + a - 1 : a - 1;\n                        const long long z = threshold >= 0 ? dp[i + 1][threshold] : 0;\n                        if (x + y - z < 0) \n                            dp[i][a] = (x + y - z + mod);\n                        else \n                            dp[i][a] = (x + y - z) % mod;\n                    }\n                } else \n                    dp[i][a] = x;\n            }\n        return dp[0][1000];\n    }\n};\n```
['C++']