Playlist

Subin solves problems at an algorithm camp while listening to music. Subin's phone stores $N$ songs, and today Subin wants to listen to $P$ songs. Subin builds a playlist that satisfies both conditions below. The same song may be added to the playlist more than once.

• Every one of the $N$ stored songs appears in the playlist at least once.
• To add a song again, at least $M$ other songs must sit between the two positions that hold it in the playlist.

A playlist is a sequence of $P$ songs, and two playlists with the same songs in a different order count separately. Given $N$, $M$, and $P$, write a program that counts the playlists Subin can build.

The first line contains $N$, $M$, and $P$, separated by spaces. ($1 \le N \le 100$, $0 \le M \le N$, $N \le P \le 100$)

Print the number of playlists Subin can build on the first line. The count can be very large, so print it modulo 1,000,000,007.

For $N = 1$, $M = 0$, $P = 3$ the only playlist is (song 1, song 1, song 1).

For $N = 1$, $M = 1$, $P = 3$ no playlist exists.

For $N = 2$, $M = 0$, $P = 3$ the playlists (song 1, song 1, song 1) and (song 2, song 2, song 2) do not count, because they leave one of the two songs out.

For $N = 2$, $M = 1$, $P = 4$ the playlists are (song 1, song 2, song 1, song 2) and (song 2, song 1, song 2, song 1).