Count Non Decreasing Arrays With Given Digit Sums
You are given an integer array digitSum of length n.
An array arr of length n is considered valid if:
0 <= arr[i] <= 5000- it is non-decreasing.
- the sum of the digits of
arr[i]equalsdigitSum[i].
Return an integer denoting the number of distinct valid arrays. Since the answer may be large, return it modulo 10^9 + 7.
An array is said to be non-decreasing if each element is greater than or equal to the previous element, if it exists.
Example 1
Input
digitSum = [25,1]Output
6Numbers whose sum of digits is 25 are 799, 889, 898, 979, 988, and 997, and the only number whose sum of digits is 1 that can appear after them while keeping the array non-decreasing is 1000.
Example 2
Input
digitSum = [1]Output
4The valid arrays are [1], [10], [100], and [1000].
Constraints
- 1 <= digitSum.length <= 1000
- 0 <= digitSum[i] <= 50