Explained 2.5 approaches O(N) O(N * M)
Approach 1: Combinatorial with Extended Euclidean (O(n))This approach uses the insight that we first need to find the minimum valid arr1:
Start with arr1[0] = 0
# Approach 1: Combinatorial with Extended Euclidean (O(n))
This approach uses the insight that we first need to find the minimum valid arr1:
1. Start with arr1[0] = 0
2. When nums[i] increases, arr1[i] must increase by at least the same amount
3. When nums[i] decreases, arr1[i] must stay equal to arr1[i-1]

After finding the minimum arr1, we calculate how much "room" we have for increasing suffixes:
```cpp
int comb_room = nums[0];  // Initial value
for (int i = 1; i < nums.size(); ++i)
    comb_room -= max(0, nums[i - 1] - nums[i]);
```

The room represents how many total increases we can distribute across n possible suffixes. This becomes equivalent to choosing k positions out of n+k total positions (where k is comb_room), giving us C(n+k,k).

The ExtEuclidInv struct implements fast modular multiplicative inverse calculation using the Extended Euclidean algorithm's recursive relationship:
```cpp
inv[n] ≡ -(⌊p/n⌋ * inv[p % n]) mod p
```

# Approach 2: Combinatorial with Fermat's Little Theorem (O(n log MOD))
This approach uses the same combinatorial logic but calculates modular inverses using Fermat's Little Theorem:
- For prime p, a^(p-1) ≡ 1 (mod p)
- Therefore, a^(p-2) is the modular multiplicative inverse of a
- We use binary exponentiation to calculate this efficiently

# Approach 3: Dynamic Programming (O(n * max(nums)))
The DP approach directly counts valid configurations:
```cpp
dp[i][j] = number of valid configurations for first i elements where arr1[i] = j
```

Key transitions:
1. For each position i, we need arr1[i] ≥ arr1[i-1]
2. arr1[i] + arr2[i] = nums[i], so arr2[i] = nums[i] - arr1[i]
3. arr2[i] must be ≤ arr2[i-1]

Uses prefix sums to handle range updates. The invariant maintained is that after processing each position i:
```cpp
dp[asc_v] = number of valid ways to achieve arr1[i] = asc_v while maintaining monotonicity
```

# Code
```cpp []
class Solution {
public:
    int countOfPairs(const vector<int>& nums) {
        return countOfPairs_comb<ExtEuclidInv>(nums);
        return countOfPairs_comb<FermatInv>(nums);
        return countOfPairs_dp(nums);
    }

    template<typename CnkT>
    int countOfPairs_comb(const vector<int>& nums) {
        int comb_room = nums[0];
        for (int i = 1; i < nums.size(); ++i)
            comb_room -= max(0, nums[i - 1] - nums[i]);

        static CnkT cnk;
        return comb_room < 0 ? 0 : cnk(nums.size() + comb_room, comb_room);
    }

    int countOfPairs_dp(const vector<int>& nums) {
        const int kDpSize = 1 + *max_element(nums.begin(), nums.end());
        vector<long long> dp(kDpSize), up_dp(kDpSize);
        fill(dp.begin(), dp.begin() + nums[0] + 1, 1); // Base

        for (int i = 1; i < nums.size(); ++i) {
            fill(up_dp.begin(), up_dp.end(), 0);
            int n = nums[i], m = nums[i - 1];
            for (int j = 1; j < dp.size(); ++j)
                dp[j] += dp[j - 1];
            for (int asc_v = 0; asc_v <= n; ++asc_v) {
                int prev_asc_lim = min(asc_v, m - n + asc_v);
                up_dp[asc_v] = (up_dp[asc_v] + (prev_asc_lim < 0 ? 0 : dp[prev_asc_lim])) % kMod;
            }
            swap(dp, up_dp);
        }

        return accumulate(dp.begin(), dp.end(), 0LL) % kMod;
    }

private:
    static constexpr long long kMod = 1e9 + 7;

    struct ExtEuclidInv {
        vector<long long> fac, inv, fac_inv;

        ExtEuclidInv() : fac(2, 1), inv(2, 1), fac_inv(2, 1) {}

        long long get_fac(int k) {
            while (fac.size() <= k)
                fac.push_back(fac.back() * fac.size() % kMod);
            return fac[k];
        }

        long long get_inv(int k) {
            while (inv.size() <= k)
                inv.push_back((kMod - (kMod / inv.size()) * inv[kMod % inv.size()] % kMod) % kMod);
            return inv[k];
        }

        long long get_fac_inv(int k) {
            while (fac_inv.size() <= k)
                fac_inv.push_back(fac_inv.back() * get_inv(fac_inv.size()) % kMod);
            return fac_inv[k];
        }

        long long operator()(int n, int k) {
            return get_fac(n) * get_fac_inv(k) % kMod * get_fac_inv(n - k) % kMod;
        }
    };

    struct FermatInv {
        vector<long long> fac, fac_inv;

        FermatInv() : fac(2, 1), fac_inv(2, 1) {}

        long long get_fac(int k) {
            while (fac.size() <= k)
                fac.push_back(fac.back() * fac.size() % kMod);
            return fac[k];
        }

        long long get_fac_inv(int k) {
            while (fac_inv.size() <= k)
                fac_inv.push_back(qpow(get_fac(fac_inv.size()), kMod - 2));
            return fac_inv[k];
        }

        long long operator()(int n, int k) {
            return get_fac(n) * get_fac_inv(k) % kMod * get_fac_inv(n - k) % kMod;
        }
    };

    static long long qpow(long long a, int p) {
        long long res = 1;
        for (; p > 0; p >>= 1) {
            if (p & 1)
                res = res * a % kMod;
            a = a * a % kMod;
        }
        return res;
    }
};

```
['C++']