<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 {
public:

ll mod = 1e9 + 7;
ll dp[101][101];

// t can be said to be time, or number of songs already chosen
// cnt is how many songs are not chosen even once
    ll f(int &n, int &g, int &k, int t, vector<int> &v, int cnt) {
        if(t == g){ //goal achieved
            return cnt == 0;  // all songs not played
        }
        if(dp[t][cnt] != -1) return dp[t][cnt];
        ll songs = 0; // stores number of songs
        for(int i = 0; i < n; i++){
            if(v[i] != -1 && t <= v[i] + k) continue; //if a song is chosen and k songs have not been players, skip it
            int p = v[i]; // for backtracking
            v[i] = t;
            songs += f(n, g, k, t+1, v, cnt - (p == -1));
            // take current songs, and decrease count if the song is chosen for the first time
            songs %= mod;
            v[i] = p; // backtracked
        }
        return dp[t][cnt] = songs % mod;
    }

    int numMusicPlaylists(int n, int g, int k) {
        memset(dp, -1, sizeof(dp));
        vector<int> v(n, -1);
        return f(n, g, k, 0, v, n);
    }
};
8000