<p>Your music player contains <code>n</code> different songs. You want to listen to <code>goal</code> songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:</p>

<ul>
	<li>Every song is played <strong>at least once</strong>.</li>
	<li>A song can only be played again only if <code>k</code> other songs have been played.</li>
</ul>

<p>Given <code>n</code>, <code>goal</code>, and <code>k</code>, return <em>the number of possible playlists that you can create</em>. Since the answer can be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, goal = 3, k = 1
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, goal = 3, k = 0
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, goal = 3, k = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= k &lt; n &lt;= goal &lt;= 100</code></li>
</ul>

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        #-i want to put a song at the end - the two types of ways I can put the song at the end:
        # 1 - the song is the first time (only time we've seen the songs) - that means there are f(n - 1, goal - 1, k) ways to arrange the previous songs, and n ways to put a song at the end
        # so the number of playlists where the last song only occurs once is n * f(n - 1, goal - 1, k)
        # 2 - the song isn't the first time it occurs - that means there are f(n, goal - 1, k) ways to arrange the previous songs BUT I can't append to ones where the song has appeared in the last k listings
        #       - how many of those previous playlists have my song in the last k listings? k/n of them
            #another way to think about it is - how many playlists are there of size goal, with n songs, with a repeat value of k, where the last song is played more than once?
            #well, for each playlist of size goal - 1, with n songs, a repeat value of k, we can append n - k different last songs to it
            #so the number of playlists where the last song occurs more than once is (n - k) * f(n, goal - 1, k)
        

        #if k > n, and n = goal then f(n, goal, k) = f(n, goal, goal) 

        #if k > n, and n < goal then return 0

        #if n > goal, then return 0

        #if n = goal, k = goal, return n * f(n - 1, goal - 1, k)

        #if n = 1, k = 1, goal = 1, return 1


        @cache
        def playlists(n, goal, k):
            if n == 1 and goal == 1:
                return 1
            if k > n and n == goal:
                return playlists(n, goal, goal)
            if k > n and n < goal or n > goal or n == 0:
                return 0
            
            return (n * playlists(n - 1, goal - 1, k) + (n - k) * playlists(n, goal - 1, k)) % (10 ** 9 + 7)
        
        return playlists(n, goal, k)
17400