Count Non-Decreasing Arrays with Prescribed Digit Sums

Given an integer array requiredSum of length n, count the distinct arrays result of length n that satisfy all three conditions:

1. result is non-decreasing: result[i] <= result[i + 1] for every adjacent pair.
2. The sum of the base-10 digits of result[i] equals requiredSum[i] at every position.
3. 1 <= result[i] <= 5000 at every position.

Return the count modulo 1000000007. Two arrays are distinct if they differ at any position. Equal adjacent values are allowed.

Input and Output

• Input: the integer array requiredSum.
• Output: one integer, the number of valid arrays modulo 1000000007. No particular valid array is required.

Constraints

• 1 <= n <= 5000.
• 1 <= requiredSum[i] <= 31 for every index.

Example 1

requiredSum = [1]
answer = 4

The possible values are 1, 10, 100, and 1000.

Example 2

requiredSum = [1, 1]
answer = 10

Each position can use one of those four values, and ten two-element arrays are non-decreasing.

Count Non-Decreasing Arrays With Required Digit Sums

Hints

1. A valid value at a position must match that position’s required digit sum.
2. Equal adjacent values are permitted by the non-decreasing condition.

Approach

For each value from 1 through 5000, compute its decimal digit sum. Let the count for a value after a position be the number of valid prefixes ending at that value. At the first position, every value with the required digit sum has count one. At each later position, a value receives the sum of prior counts at values no greater than itself, but only if its own digit sum matches the requirement. A left-to-right prefix sum computes those transitions in one scan. The invariant counts every valid array exactly once by its final value, including equal adjacent values. Modulo arithmetic preserves the requested result.

• Time complexity: O(n × 5000), where n is the length of requiredSum.
• Space complexity: O(5000) for digit sums and two count arrays.