JOIN
Get Time

   Problem Statement  

 Problem Statement for NoRepeatPlaylist

Problem Statement

    

Michael loves listening to music from his cell phone while travelling by train. He currently has N songs in his cell phone. During one trip he has the time to listen to P songs. So his cell phone creates a playlist of P (not necessarily different) songs according to the following rules:

  • Each song has to be played at least once.
  • At least M songs have to be played between any two occurrences of the same song. (This ensures that the playlist is not playing the same song too often.)

Michael wonders how many different playlists his cell phone can create. You are given the ints N, M, and P. Let X be the number of valid playlists. Since X can be too large, your method must compute and return the value (X modulo 1,000,000,007).

 

Definition

    
Class:NoRepeatPlaylist
Method:numPlaylists
Parameters:int, int, int
Returns:int
Method signature:int numPlaylists(int N, int M, int P)
(be sure your method is public)
    
 

Notes

-Two playlists A and B are different if for some i between 1 and P, inclusive, the i-th song in A is different from the i-th song in B.
 

Constraints

-N will be between 1 and 100, inclusive.
-M will be between 0 and N, inclusive.
-P will be between N and 100, inclusive.
 

Examples

0)
    
1
0
3
Returns: 1
You have only 1 song which can be played as often as you want.

So the only valid playlist is: {song1, song1, song1}.
1)
    
1
1
3
Returns: 0
Now is the same scenario as in Example 0, but the song cannot be played 2 times in a row.

Thus there is no valid playlist.
2)
    
2
0
3
Returns: 6
Now you have 2 songs and you can play them as often as you want.

Just remember that playlists {song1, song1, song1} and {song2, song2, song2} are not valid, because each song must be played at least once.
3)
    
4
0
4
Returns: 24
You have time to play each song exactly once. So there are 4! possible playlists.
4)
    
2
1
4
Returns: 2
The only two possibilities are {song1, song2, song1, song2} and {song2, song1, song2, song1}.
5)
    
50
5
100
Returns: 222288991

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 531 Round 1 - Division I, Level One
       Single Round Match 531 Round 1 - Division II, Level Two