C++ | DP | O(n*m) | Prefix Sum
\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        int n=nums.size(),ans=0,module=1000000007,count=0,currNum,sum=0,first,second,val
```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        int n=nums.size(),ans=0,module=1000000007,count=0,currNum,sum=0,first,second,val;\n        vector<vector<int>> dp(n,vector<int>(2001,0));\n        vector<int> preSum(2001,0);\n        for(int index=0;index<=nums[0];index++) {\n            dp[0][index]=1;\n            sum++;\n            preSum[index]=sum;\n        }\n\n        for(int row=1;row<n;row++) {\n            for(int col=0;col<=nums[row];col++) {\n                val=nums[row]-col;\n                if(val<=nums[row-1]) {\n                    dp[row][col]=preSum[min(nums[row-1]-val,col)];    \n                }\n            }\n            sum=0;\n            \n            for(int col=0;col<=nums[row];col++) {\n                sum=((long long int)sum+dp[row][col])%module;\n                preSum[col]=sum;\n            }\n        }\n\n        for(int col=0;col<=nums[n-1];col++) {\n            ans=((long long int)ans+dp[n-1][col])%module;\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C', 'Prefix Sum']