No dynamic programming
Intuition\nGoing from left to right we can determine the effective size of possible values for each number. It turns out that this size is the same for all numb
# Intuition\nGoing from left to right we can determine the effective size of possible values for each number. It turns out that this size is the same for *all* numbers. Knowing this size we can compute the result directly. Dynamic Programming is not necessary at all.\n\n# Approach\nFirst go from `num[0]` to `num[-1]` shrinking all numbers. The final size `k := num[-1]` is the effective size of all numbers, hence the solution corresponds to the solution of `num = [k, k, ..., k]` where `n = num.len()`. The number of solutions is then the number of possible paths from `(0,0)` to `(n,k)` in an `k \xD7 n` lattice that move only right or upwards in each step. The total number of these paths is $\\binom{n+k}{k}$.\n\nThe only computational challenge is therefore to compute the binomal coefficient $\\binom{n+k}{k} \\mod (10^9+7)$. Unfortunately Rust\'s standard library does not have arbitrarily large integers, hence this is a little tricky.\n\nThe chosen approach is to compute $\\binom{n+k}{k} = \\frac{n!}{k!(n-k)!}$ by computing all prime factors for $n!$, $k!$ and $(n-k)!$ and cancel out the corresponding factors in $n!$. The result is then the product of the remaining prime factors of $n!$ modulo $10^9+7$, which can be computed easily.\n\n# Complexity\n- Time complexity: $O(n + T(\\operatorname{binom}))$\n\n  - $O(n)$ for reading the input in order to compute $k$.\n  - $O(T(\\operatorname{binom}))$ for computing the prime factorization of $n!$, which should be $O(n^2)$, but since $n$ is rather small (\u2264 1000) it is negligible.\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimpl Solution {\n    pub fn count_of_pairs(mut nums: Vec<i32>) -> i32 {\n        let mut diff = 0;\n        for k in 1..nums.len() {\n            diff += 0.max((nums[k] - diff) - nums[k - 1]);\n            nums[k] -= diff;\n            if nums[k] < 0 {\n                return 0;\n            }\n        }\n\n        let n = nums.len();\n        let k = nums[n-1] as usize;\n        binomial(n + k, k)\n    }\n}\n\nfn primes_upto_n(n: usize) -> impl Iterator<Item=u16> {\n    let mut is_prime = vec![true; n + 1];\n    is_prime[0] = false;\n    is_prime[1] = false;\n    for k in 2..=n / 2 {\n        if is_prime[k] {\n            let mut m = k + k;\n            while m <= n {\n                is_prime[m] = false;\n                m += k;\n            }\n        }\n    }\n    is_prime\n        .into_iter()\n        .enumerate()\n        .filter_map(|(i, p)| p.then_some(i as u16))\n}\n\nfn primes_of_factorial(n: usize) -> impl Iterator<Item=(u16, u16)> {\n    primes_upto_n(n).map(move |p| {\n        let mut k = 0;\n        let mut j = usize::from(p);\n        while j <= n {\n            k += n / j;\n            j *= usize::from(p);\n        }\n        (p, k as u16)\n    })\n}\n\nfn binomial(n: usize, k: usize) -> i32 {\n    if k > n {\n        return 0;\n    }\n    if k == 0 || k == n {\n        return 1;\n    }\n\n    let primes_of_n = primes_of_factorial(n);\n    let mut primes_of_k = primes_of_factorial(k).peekable();\n    let mut primes_of_nk = primes_of_factorial(n - k).peekable();\n\n    primes_of_n.fold(1, move |prod, (p, mut cnt)| {\n        if Some(p) == primes_of_k.peek().map(|p| p.0) {\n            cnt -= primes_of_k.next().unwrap().1;\n        }\n\n        if Some(p) == primes_of_nk.peek().map(|p| p.0) {\n            cnt -= primes_of_nk.next().unwrap().1;\n        }\n\n        (prod * u64::from(p).pow(u32::from(cnt))) % 1_000_000_007\n    }) as i32\n}\n\n```
['Rust']