<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:
    long long mod=1e9+7;
    long long solve(vector<vector<long long>>&dp, long long n, long long pos, long long goal, long long k, unordered_map<long long,long long>& lastPos, long long cnt){
        if(pos==goal+1) return cnt==0;
        if(dp[pos][cnt]!=-1) return dp[pos][cnt];
        long long count=0;
        for(long long i=1; i<=n; i++){
            if(lastPos[i]!=0 && pos-lastPos[i]<=k){
                continue;
            }
            long long prev = lastPos[i];
            lastPos[i]=pos;
            count+=solve(dp,n,pos+1, goal,k , lastPos, cnt-(prev==0));
            count%=mod;
            lastPos[i]=prev;
        }
        return dp[pos][cnt]=count%mod;
    }
    int numMusicPlaylists(int n, int goal, int k) {
        // if(n==goal){
        //     long long fact=n;
        //     n--;
        //     while(n){
        //         fact*=n;
        //         n--;
        //     }
        //     return fact;
        // }
        unordered_map<long long,long long>lastPos;
        vector<vector<long long>>dp(goal+1,vector<long long>(n+1,-1));
        return solve(dp,n,1,goal,k,lastPos,n);
    }
};
12300