Number of Music Playlists

Create an ordered playlist of exactly goal entries using n distinct songs. Every song must appear at least once. Before a song can play again, at least k other songs must have played since its previous appearance; equivalently, a song cannot match any of the previous k entries. Return the number of valid playlists modulo 1000000007. When k is zero, immediate repetition is allowed.

Example 1:

Input: n = 2
goal = 4
k = 1

Output: 2

Explanation: A song cannot repeat immediately, so the songs must alternate. The two playlists are [1,2,1,2] and [2,1,2,1].

Example 2:

Input: n = 2
goal = 4
k = 0

Output: 14

Explanation: There are 2^4=16 length-four sequences using the two songs. Exclude [1,1,1,1] and [2,2,2,2], which each omit a song. The remaining 14 playlists qualify.

Example 3:

Input: n = 1
goal = 3
k = 0

Output: 1

Explanation: There is only one song, and immediate repetition is allowed. The sole playlist is [1,1,1].

Constraints:

• 0 <= k < n <= goal <= 100