<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:
    #define MOD 1000000007
    vector<int> freq;
    vector<int> last_used;
    int n = 0;
    int k = 0;
    int dp[101][101][101];
    int util(int i, int uq, int goal, int cnt) {
        int ans = 0;
        if (goal == 0) {
            // cout<<uq<<" "<<k<<endl;
            if (uq == n) return 1;
            return 0;
        }
        if (dp[i][uq][goal] != -1) return dp[i][uq][goal];


        for (int j=1; j<=n; j++) {
            if (freq[j] == 0) {
                freq[j]++;
                int temp = last_used[j];
                last_used[j] = cnt;

                ans = ans % MOD + util(j, uq+1, goal-1, cnt+1) % MOD;

                freq[j]--;
                last_used[j] = temp;
            }
            else {
                if (cnt - last_used[j] - 1 >= k) {
                    freq[j]++;
                    int temp = last_used[j];
                    last_used[j] = cnt;

                    ans = ans % MOD + util(j, uq, goal-1, cnt+1) % MOD;

                    freq[j]--;
                    last_used[j] = temp;
                }
            }
        } 

        return dp[i][uq][goal] = ans % MOD;

        // if (k > 0) {
        //     for (int j=1; j<=n; j++) {
        //         if (freq[j] == 0) {
        //             freq[j]++;
        //             ans += util(j, uq+1, goal-1, k-1);
        //             freq[j]--;
        //         }
        //     }  
            
        // } else {
        //     for (int j=1; j<=n; j++) {
        //         if (freq[j] == 0) {
        //             freq[j]++;
        //             ans += util(j, uq+1, goal-1, k-1);
        //             freq[j]--;
        //         }
        //         else {
        //             freq[j]++;
        //             ans += util(j, uq, goal-1, k-1);
        //             freq[j]--;
        //         }
        //     }
        // }

        return ans;
    }
    int numMusicPlaylists(int m, int goal, int l) {
        n = m;
        k = l;
        memset(dp, -1, sizeof(dp));
        freq.resize(n+1, 0);
        last_used.resize(n+1, 0);
        return util(0, 0, goal, k);
    }
};
12400