<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 {
public:
int mod= 1e9 + 7;
/*
tc: O(N∗K∗Goal)
mikeeee
Knapsack pattern: each time two choices
 . play a unique song   
 . replay a song
*/
#define ll long long int
    ll solve(ll songs_played, ll unique_cnt, int goal, int n, int k,vector<vector<ll>>&dp){
        // playlist formed
        if(songs_played==goal){
            return unique_cnt==n;// all songs played atleast once
        }
        if(dp[songs_played][unique_cnt] !=-1) return dp[songs_played][unique_cnt];
        // play unique song
        // multiplying not adding kyunki abhi  task fininsh nhi hua kyunki 
        // we have to use all the unique songs [counting principle]
        ////eg.  A, B, C   k=2 and goal=10
       ll  old_songs = (n - unique_cnt) * solve(songs_played+1, unique_cnt+1, goal, n, k,dp);

        // replay song
        // after this, all the gaps have only (unique_cnt - k) choices
        //eg.  A, B, C   k=2 and goal=10    till now unique_cnt=3 A,B,C,_(A),_(B)....
        ll new_songs = max(unique_cnt - k, 0ll) * solve(songs_played+1, unique_cnt, goal, n, k,dp);
        ll ans = (old_songs %mod + new_songs%mod) %mod;
        return dp[songs_played][unique_cnt]= ans %mod;
    }
    int numMusicPlaylists(int n, int goal, int k) {
        vector<vector<ll>>dp(goal+1, vector<ll>(goal+1,-1));
        return solve(0,0,goal,n,k,dp);
    }
};
11500