Microsoft Software Engineer Interview Experience — A 90-Minute OA and Only Time for Brute Force

The latest OA: 90 minutes, two questions, with AI hints for the second question. I only managed to write a brute-force solution for the second one. It probably needed DP, but I ran out of time.
2571
You are given an integer array requiredSum of length n. Build an array result of length n that satisfies all of these conditions:
1.        result is non-decreasing: result[i] ≤ result[i + 1] for every valid i.
2.        The sum of the digits of result[i] equals requiredSum[i].
3.        1 ≤ result[i] ≤ 5000.
Return the number of distinct arrays result that can be built, modulo 10^9 + 7.
Example
•        Input: requiredSum = [1]
•        Output: 4
•        Explanation: The valid values are 1, 10, 100, and 1000, each with digit sum 1.
Constraints
•        1 ≤ n ≤ 5000
•        1 ≤ requiredSum[i] ≤ 31