## Algorithm

Problem Name: 920. Number of Music Playlists

Your music player contains `n` different songs. You want to listen to `goal` songs (not necessarily different) during your trip. To avoid boredom, you will 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.

Given `n`, `goal`, and `k`, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo `109 + 7`.

Example 1:

```Input: n = 3, goal = 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], and [3, 2, 1].
```

Example 2:

```Input: n = 2, goal = 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], and [1, 2, 2].
```

Example 3:

```Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].
```

Constraints:

• `0 <= k < n <= goal <= 100`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int numMusicPlaylists(int N, int L, int K){
long *dp;
int i, j, x;

// dp[i][j]: number of possible answers on listening to i with j songs
// then we want to get dp[L][N]
dp = calloc((L + 1) * (N + 1), sizeof(*dp));
//assert(dp);
#define IDX(I, J) ((I) * (N + 1) + (J))

dp[IDX(0, 0)] = 1;

for (i = 1; i  < = L; i ++) {
for (j = 1; j  < = N; j ++) {
x = N - j + 1;      // number of songs not being selected (including current song j)
dp[IDX(i, j)] = dp[IDX(i - 1, j - 1)] * x;  // choose a new song

x = j - K;          // number of played songs (including song j) can be re-selected
if (x > 0) {
dp[IDX(i, j)] += dp[IDX(i - 1, j)] * x; // choose a played songs
}
dp[IDX(i, j)] %= 1000000007;
}
}

i = dp[IDX(L, N)];

free(dp);

return i;
}
``````
Copy The Code &

Input

cmd
n = 3, goal = 3, k = 1

Output

cmd
6

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numMusicPlaylists = function (N, L, K) {
const mod = 10 ** 9 + 7
const dp = Array.from({ length: L + 1 }, () => Array(N + 1).fill(0))
dp[0][0] = 1
for (let i = 1; i  < = L; i++) {
for (let j = 1; j  < = N; j++) {
dp[i][j] = (dp[i - 1][j - 1] * (N - (j - 1))) % mod
if (j > K) {
dp[i][j] = (dp[i][j] + ((dp[i - 1][j] * (j - K)) % mod)) % mod
}
}
}
return dp[L][N]
}
``````
Copy The Code &

Input

cmd
n = 3, goal = 3, k = 1

Output

cmd
6

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
from functools import lru_cache

class Solution:
def numMusicPlaylists(self, N, L, K):
@lru_cache(None)
def dp(i, j): return +(j == 0) if not i else (dp(i-1, j-1) * (N-j+1) + dp(i-1, j) * max(j-K, 0)) % (10**9+7)
return dp(L, N)
``````
Copy The Code &

Input

cmd
n = 2, goal = 3, k = 0

Output

cmd
6