920. Number of Music Playlists

Hard

876

91

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** `10`

.^{9} + 7

**Example 1:**

Input:n = 3, goal = 3, k = 1Output:6Explanation: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 = 0Output:6Explanation: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 = 1Output:2Explanation:There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

**Constraints:**

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

Accepted

22.4K

Submissions

44.2K

Acceptance Rate

50.7%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved