Count non-decreasing arrays by digit sums

You are given an array required_sums of length n. Count how many non-decreasing arrays result[1..n] of integers satisfy all of the following: ( 1) for each i, digit_sum(result[i]) = required_sums[i]; ( 2) for each i, result[i] ≤ 5000; and ( 3) for i > 1, result[i] ≥ result[i−1]. Two arrays are distinct if they differ at any index. Return the count modulo 1,000,000,007. Describe an efficient algorithm and analyze its time and space complexity.