human
Solve in Python:
Your music player contains N different songs and she wants to listen to L (not necessarily different) songs during your trip.  You create a playlist so that:

Every song is played at least once
A song can only be played again only if K other songs have been played

Return the number of possible playlists.  As the answer can be very large, return it modulo 10^9 + 7.
 


Example 1:
Input: N = 3, L = 3, K = 1
Output: 6
Explanation: There are 6 possible playlists. [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

Example 2:
Input: N = 2, L = 3, K = 0
Output: 6
Explanation: There are 6 possible playlists. [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2]

Example 3:
Input: N = 2, L = 3, K = 1
Output: 2
Explanation: There are 2 possible playlists. [1, 2, 1], [2, 1, 2]


 
Note:

0 <= K < N <= L <= 100
assistant
#Here is the Python code you requested.

class Solution:
    import math
    from functools import lru_cache
    def numMusicPlaylists(self, N: int, L: int, K: int) -> int:
        MOD = 1000000007

        @lru_cache(maxsize=None)
        def rec(n, l):
            if l < n or n <= K:
                return 0
            elif l == n:
                return math.factorial(n) % MOD
            return (n * rec(n - 1, l - 1) + (n - K) * rec(n, l - 1)) % MOD

        return rec(N, L)