A bar of music lasts n beats. A drummer plays hits whose durations come from the list steps (distinct positive integers, unlimited reuse) one after another until the bar is exactly full. Two patterns are different if the sequence of durations differs, so [1, 2] and [2, 1] are two patterns. Return the number of patterns modulo 10**9 + 7. A bar of 0 beats has one pattern (play nothing).
Examples
Input: n = 4, steps = [1, 2]
Output: 5
Explanation: 1111, 112, 121, 211, 22.
Input: n = 5, steps = [2, 3]
Output: 2
Explanation: 23 and 32.
Constraints
0 <= n <= 10**51 <= len(steps) <= 10,1 <= steps[i] <= 50, all distinct- Target complexity: O(n * len(steps)) time.
Goals
- Count ordered sequences that sum to a target with a one-dimensional table
- Distinguish ordered compositions from unordered combinations