Count Fixed-Length Playlists That Use Every Song with a Replay Gap

### Problem Create an ordered playlist of length `goal` from n distinct songs. Every song must appear at least once. After a song is played, at least k other songs must be played before it can play again. Return the number of valid playlists modulo `10^9+7`. ```cpp class Solution { public: int numMusicPlaylists(int n, int goal, int k); }; ``` ### Examples **Example 1:** ```text Input: n = 3, goal = 4, k = 1 Output: 18 Explanation: There are3*2^3=24 sequences without equal neighbors. Six use only a chosen pair of songs, leaving18 that use all three. ``` **Example 2:** ```text Input: n = 2, goal = 4, k = 0 Output: 14 Explanation: Of2^4=16 playlists, exclude the two constant playlists that omit one song. ``` ### Constraints - `0 <= k < n <= goal <= 100`. ### Contract considerations A replay gap is measured in intervening plays. The rule itself ensures the most recent k plays are distinct. ```hint Read the boundary condition At each extension, distinguish a never-used song from an eligible previously used song. ``` ### Boundary reminders A replay gap is measured in intervening plays. The rule itself ensures the most recent k plays are distinct.