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

#define ll long long
class Solution {
    int MOD = 1000000007;
private:
    int solve(int totalSongs, int totalUniqueSongs, int n, int goal, int k, vector<vector<int>> &dp){
        // base case
        if(totalSongs==goal){
            if(totalUniqueSongs==n){
                return 1;
            }
            return 0;
        }

        if(dp[totalSongs][totalUniqueSongs]!=-1) return dp[totalSongs][totalUniqueSongs];

        int ans = 0;
        if(totalUniqueSongs<n){
            int remUniqueSongs = n - totalUniqueSongs;
            ans = (ans + (ll)remUniqueSongs*(solve(totalSongs+1, totalUniqueSongs+1, n, goal, k, dp)%MOD))%MOD;
        }

        if(totalUniqueSongs>k){
            int totalReplaySongs = totalUniqueSongs - k;
            ans = (ans + (ll)totalReplaySongs*(solve(totalSongs+1, totalUniqueSongs, n, goal, k, dp)%MOD))%MOD;
        }

        return dp[totalSongs][totalUniqueSongs] = ans%MOD;
    }
public:
    int numMusicPlaylists(int n, int goal, int k) {
        vector<vector<int>> dp(goal+1,vector<int>(n+1,-1));
        return solve(0,0,n,goal,k,dp);
    }
};
// class Solution {
// public:
//     int numMusicPlaylists(int N, int goal, int K) {
//         const int MOD = 1e9 + 7;

//         // dp[i][j] represents the number of playlists of length j with i unique songs
//         vector<vector<long long>> dp(N + 1, vector<long long>(goal + 1, 0));

//         // There's only one way to arrange zero songs (an empty playlist)
//         dp[0][0] = 1;

//         // Fill the dp table
//         for (int i = 1; i <= N; ++i) {
//             for (int j = 1; j <= goal; ++j) {
//                 // Case 1: We add a new unique song
//                 dp[i][j] = dp[i - 1][j - 1] * (N - (i - 1)) % MOD;
                
//                 // Case 2: We add a song that was played before (but after K songs)
//                 if (i > K) {
//                     dp[i][j] = (dp[i][j] + dp[i][j - 1] * (i - K) % MOD) % MOD;
//                 }
//             }
//         }

//         return dp[N][goal];
//     }
// };
9500