#920
Number of Music Playlists
expert · 1185 · lc hard +32 · verified · 60% accepted · 2,462 likes · top 58%
Description
You have n unique songs and want to create a playlist of exactly goal plays. Two rules apply:
- Each of the n songs must be included at least once.
- A song cannot be repeated unless at least k other distinct songs have been played since its last appearance.
Return the number of valid playlists modulo 109 + 7.
Example 1:
Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
Example 2:
Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].
Example 3:
Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].
Code
1
2
3