<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:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        # return 0
        # generate the # of combination + shift
        # 3, 1, 1 
        # [3]
        # 3, 2, 1
        # [3,2]
        # (3,3,1) = (2,2,1) * 3 + (3,2,1) * (3-1)
        # (2,2,1) = (1,1,1) * 2
        # (3,4,1) = (2,3,1) * 3 + (3,3,1) * (3-1)
        # DP i => position of the occ on this position
        # DP
        # [...],
        # [...],
        # DP[i][j] each 
        # f(n,g,k) = f(n-1,g-1,k) * n + f(n,g-1,k) * (n-k)
        # 3,4,2 = 2,3,2 * 3 + 3,3,2 * (3-2)
        # Recursion solv
        @cache
        def helper(n,g,k):
            print(n,g,k,"reciving")
            if n > g or g == k:
                return 0
            if g == 1:
                return n
            if n <= 0 or g <=0:
                return 0
            
            if n == g:
                # The factorial
                return math.factorial(n)
            
            res1 = helper(n-1,g-1,k) * n
            res2 = helper(n,g-1,k) * (n-k)
            res = res1 + res2
            
            print(res, f"n{n} g{g} k{k}")
            return res % (10**9 + 7)
        
        return helper(n,goal,k) % (10**9 + 7)



        




17900