JOIN

 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