<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>

MOD = 10**9 + 7


class Solution:

    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, goal + 1):
            new_dp = [0] * (n + 1)
            for j in range(1, min(i + 1, n + 1)):
                # Baseline: choose a totally new song
                new_dp[j] = dp[j - 1] * (n - (j - 1)) % MOD
                
                if j > k:
                    # Bonus: can repeat song now, choose anyone except k
                    new_dp[j] += dp[j] * (j - k)
                    new_dp[j] %= MOD
            
            dp = new_dp
        
        return dp[n]


    # def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
    #     # dp[i][j] : play i total # of songs, with j distinct songs.
    #     dp = [[0] * (n + 1) for _ in range(goal + 1)]
    #     dp[0][0] = 1
    #     for i in range(1, goal + 1):
    #         for j in range(1, n + 1):
    #             # Baseline: choose a totally new song
    #             num_new_songs = dp[i - 1][j - 1] * (n - (j - 1)) % MOD
    #             dp[i][j] = num_new_songs
    #             if j > k:  # Bonus: can repeat song now, choose anyone except k
    #                 dp[i][j] += (dp[i - 1][j] * (j - k)) % MOD
    #                 dp[i][j] %= MOD
    #     return dp[goal][n]
16700