Number of Music Playlists

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:

1. 0 <= K < N <= L <= 100

class Solution {
    public int numMusicPlaylists(int N, int L, int K) {
        int mod = 1_000_000_007;
        // dp[i][j] => Number of playlists, if we want to listen to i songs & we have j
        // distinct songs (j<=i)
        long[][] dp = new long[L + 1][N + 1];
        // Only 1 playlist possible if we don't want to listen to any song
        dp[0][0] = 1;
        for (int i = 1; i <= L; i++) {
            // By loop from 1->i, we are making sure that j<=i is maintained
            for (int j = 1; j <= i && j <= N; j++) {
                // If we choose a new Song to listen to
                // We can choose from the remaining N - (j - 1) songs
                dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1))) % mod;
                // If we choose an old song,
                // then we need to make sure that k distinct songs have been already played
                // dp[i-1][j] * (j-K) -> Out of the 'j' distinct songs, we are choosing from
                // j-K, because we want k different songs to be played before this song
                if (j > K)
                    dp[i][j] = (dp[i][j] + (dp[i - 1][j] * (j - K)) % mod) % mod;
            }
        }
        return (int) dp[L][N];
    }
}