Count Valid Recommendation Playlists
A recommender assembles a playlist of fixed length from a catalog. Every track in the catalog must appear, and a track may repeat only after at least k other tracks have played since its last appearance. Count the distinct ordered playlists.
Problem
Given n unique tracks, build playlists of length goal such that every track is used at least once and any track repeat happens only after at least k other tracks have played in between. Return the number of possible playlists modulo 1e9+7.
Input
Three integers n (catalog size), goal (playlist length), and k (repeat cooldown).
Output
An integer: the count of valid playlists modulo 1e9+7.
Constraints
- 0 <= k < n <= 100
- n <= goal <= 100
- Answer is taken modulo 1_000_000_007.
Examples
Example 1
Input
n = 3, goal = 3, k = 1
Output
6
All 3! orderings of three distinct tracks are valid.
Example 2
Input
n = 2, goal = 3, k = 1
Output
2
[1,2,1] and [2,1,2] are the only valid playlists.