Linear solution using combinatorics.
Intuition\n Describe your first thoughts on how to solve this problem. \nUse combinatorics to find the answer.\n\nTake the last element from nums and subtract a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse combinatorics to find the answer.\n\nTake the last element from `nums` and subtract all the **increases** from `nums`. If the result `x` is negative, then the answer is 0. Otherwise, the answer is `x + n` chooses `n`.\n\n# Approach\n\nLet\'s explain this approach using the examples from the problem description.\n\n---\nExample 1:\n\n`nums = [2, 3, 2]`\n\nLet\'s find the minimum non-decreasing sequence `arr1` we can find.\n\nWe can see that the minimum non-decreasing sequence `arr1` would be `[0, 1, 1]` (The corresponding `arr2` would be `[2, 2, 1]`). This sequence will always starts with `0`, and increases only when `nums` increases, and it should increase the same amount. When `nums` decreases, `arr1` will remain unchanged.\n\nIf `arr1[n - 1]` is greater than `nums[n - 1]`, then there will be no valid result.\n\nOtherwise, you can notice that, if you increase any suffix of `arr1` by `1`, as long as `arr1[n - 1]` is not greater than `nums[n - 1]`, the resulting array will be still non-decreasing, and it will still be a valid result. This is because when you do this, effectively you also decrease the corresponding suffix in `arr2` by `1`. So `arr2` will also remain non-increasing and `arr2[n - 1] = nums[n - 1] - arr1[n - 1] >= 0`\n\ne.g. `[0, 1, 1] -> [0, 1, 2]` is a valid example. `[0, 1, 1] -> [0, 2, 2]` is also a valid example. `[0, 1, 1] -> [1, 2, 2]` is also a valid example.\n\nTherefore, the maximum number of times you can perform the above operations, is `nums[n - 1] - arr1[n - 1]` since due to the restriction from the last element.\n\nSince there are `n` different suffix, so the number of different new `arr1` you can get, is equal to the number of different way you can put `nums[n - 1] - arr1[n - 1]` balls into `n + 1` bins. (the additional bin simply means don\'t perform any operations).\n\nBased on the balls and bins formula, the answer is $$\\binom{\\text{nums}[n - 1] - \\text{arr1}[n - 1] + n}{n}$$\n\n---\n\nExample 2:\n`nums = [5, 5, 5, 5]`\n\nThe minimum non-decreasing sequence `arr1` we can find is `[0, 0, 0, 0]`.\n\nThere are `4` different suffix we can add. The maximum number of operations we can perform is `5 - 0 = 5`.\n\nOne possible result is `[2, 2, 3, 4, 4]`. This can be obtains by perform twice on the whole array, once on the last three elements and once on the last two elements.\n\nSo the answer is equal to putting `5` balls into `5` bins (again, one addditional bin for not performing operations on any suffix). The answer is $$\\binom{5 + 4}{4}=126$$ \n\n# Complexity\n- Time complexity: $$O(N + \\max(\\text{nums}))$$. We can precompute all the `K!` and `1 / K!` for all `1 <= K <= N + M `\n\n- Space complexity: $$O(N + \\max(\\text{nums}))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nconst int MAXN = 2000;\nconst int MAXV = 1000;\nconst int MAXF = MAXN + MAXV + 10;\nconst long long MOD = 1000000007;\n\nlong long factorial[MAXF];\nlong long invFactorial[MAXF];\nlong long inv[MAXF];\n\nbool hasPreprocess = false;\n\nvoid preprocess() {\n    if (hasPreprocess) {\n        return;\n    }\n    hasPreprocess = true;\n    factorial[0] = 1;\n    invFactorial[0] = 1;\n    inv[0] = 1;\n    factorial[1] = 1;\n    invFactorial[1] = 1;\n    inv[1] = 1;\n    for (int i = 2; i < MAXF; i++) {\n        factorial[i] = factorial[i - 1] * i % MOD;\n        inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;\n        invFactorial[i] = invFactorial[i - 1] * inv[i] % MOD;\n    }\n}\n\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        preprocess();\n        int n = nums.size();\n        int count = nums[n - 1];\n        for (int i = 1; i < n; i++) {\n            count -= max(0, nums[i] - nums[i - 1]);\n        }\n        if (count < 0) {\n            return 0;\n        }\n        return factorial[count + n] * invFactorial[n] % MOD * invFactorial[count] % MOD;\n    }\n};\n```
['Combinatorics', 'C++']