Count Nondecreasing Arrays with Prescribed Digit Sums

# Count Nondecreasing Arrays with Prescribed Digit Sums You are given an integer array `digitSum` of length `n`. Count the distinct integer arrays `arr` of the same length that satisfy all of the following: - Every entry is in the inclusive range `0 <= arr[i] <= 5000`. - The array is nondecreasing: `arr[i - 1] <= arr[i]` for every `i > 0`. - The sum of the decimal digits of `arr[i]` equals `digitSum[i]`. Return the count modulo `1000000007`. The decimal digit sum of `0` is `0`. Arrays are distinguished by their integer entries, and equal neighboring entries are allowed. ### Function `int countArrays(vector<int>& digitSum)` ### Example 1 **Input:** `digitSum = [1, 1]` **Output:** `10` **Explanation:** Within the permitted range, the integers with digit sum `1` are `1`, `10`, `100`, and `1000`. There are ten nondecreasing pairs: four starting with `1`, three starting with `10`, two starting with `100`, and one starting with `1000`. ### Example 2 **Input:** `digitSum = [1, 0]` **Output:** `0` **Explanation:** The second entry would have to be `0`, while the first entry would have to be one of `1`, `10`, `100`, and `1000`. None of these pairs is nondecreasing. ### Constraints - `1 <= digitSum.length <= 1000` - `0 <= digitSum[i] <= 50` - Every value chosen for `arr` must lie in `[0, 5000]`. ### Clarifications - The upper bound `5000` is included. - Equal values at different positions do not make an array invalid. - If a requested digit sum has no suitable integer at a position, that choice contributes no valid arrays. ### What a Strong Answer Covers - Counting integer arrays without counting alternate digit representations or construction histories. - Handling zero, equality and digit sums with no legal value. - Computing the correct modular count efficiently for all `1000` positions.