number-of-music-playlists

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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:

<ul>
	<li>Every song is played at least once.</li>
	<li>A song can only be played again only if <code>k</code> other songs have been played.</li>
</ul>

Given <code>n</code>, <code>goal</code>, and <code>k</code>, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo <code>109 + 7</code>.
&nbsp;
Example 1:

<pre>
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].
</pre>

Example 2:

<pre>
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].
</pre>

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= k &lt; n &lt;= goal &lt;= 100</code></li>
</ul>