플레이리스트

수빈이는 알고리즘 캠프에서 음악을 들으면서 문제를 풀고 있다. 수빈이의 스마트폰에는 노래 $N$개가 저장되어 있고, 오늘 수빈이는 노래 $P$곡을 들으려고 한다. 수빈이는 다음 두 조건을 모두 만족하는 플레이리스트를 만들려고 한다. 플레이리스트에는 같은 노래를 여러 번 추가해도 된다.

• 저장된 노래 $N$개가 모두 플레이리스트에 한 번 이상 나와야 한다.
• 같은 노래를 다시 추가하려면, 플레이리스트에서 그 두 자리 사이에 다른 곡이 적어도 $M$개 있어야 한다.

플레이리스트는 길이가 $P$인 노래 순서열이고, 순서가 다르면 서로 다른 플레이리스트로 센다. $N$, $M$, $P$가 주어졌을 때, 수빈이가 만들 수 있는 플레이리스트의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$, $M$, $P$가 공백으로 구분되어 주어진다. ($1 \le N \le 100$, $0 \le M \le N$, $N \le P \le 100$)

첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 개수를 출력한다. 개수가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

$N = 1$, $M = 0$, $P = 3$이면 가능한 플레이리스트는 (노래1, 노래1, 노래1) 하나뿐이다.

$N = 1$, $M = 1$, $P = 3$이면 가능한 플레이리스트가 없다.

$N = 2$, $M = 0$, $P = 3$일 때 (노래1, 노래1, 노래1)과 (노래2, 노래2, 노래2)는 노래 두 개를 모두 쓰지 않으므로 세지 않는다.

$N = 2$, $M = 1$, $P = 4$이면 가능한 플레이리스트는 (노래1, 노래2, 노래1, 노래2)와 (노래2, 노래1, 노래2, 노래1) 둘이다.