Prob No.0000 : 탈출 [CH02.2.Algorithm(Design)]

Time Limit(Test case) : 1000(ms)

[koistudy.net (32nd 유재민)]

Background

 comet은 시설 사용을 잘못해서 사감선생님의 진노를 샀다.
화가 난 사감선생님은 comet을 원형 미로에 가두어 버렸고 comet은
매일 M 이하의 칸만큼 이동을 해야하는 벌을 받게 되었다. 
원형 미로는 N개의 칸으로 구성되어 있으며 i(0<i<N-1)번째 칸은 i-1,i+1 칸과 인접해 있다.
0번 칸은 N-1,1번 칸과 이웃해 있고 N-1번 칸은 N-2,0번 칸과 이웃해 있다.
comet은 반드시 하루에 1칸 이상 이동해야 한다.
comet은 미로를 탈출하고자 노력한 끝에 D일 후에 0번 칸에서 출구가 열린다는 사실을 깨달았다.
하지만 안타깝게도 comet은 매일 자기가 원하는 만큼 이동할 수 없다. 
매일 이동해야 하는 칸의 수는 사감선생님이 임의로 정해주기 때문에 comet은 D일 후에 0번째 칸에 도달하지 못할 수도 있다.
comet이 알고 있는 것은 사감선생님이 반드시 1이상 M이하의 칸 만큼만 이동하라고 한다는 사실이다.
또, 사감선생님은 1부터 M까지의 수들을 똑같은 확률로 고른다.
comet은 자신이 탈출할 수 있는 경우의 수가 궁금해졌다.
comet에게 탈출할 수 있는 경우의 수를 구해서 알려주자.
(comet은 0번째 일에 0번째 칸에 있다.)

(단, 경우의 수가 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력하라)



Input
첫번째 줄에 칸의 수 N, 이동하는 칸의 범위 M, 출구가 열리는 날인 D가 입력된다.


[SubTask Info]
#1 (10%) : N<100 , M<N, D<100
#2 (10%) : N<100 , D<100
#3 (15%) : N<100 , D<1,000,000
#4 (30%) : N<100 , D<1,000,000,000
#5 (35%) : N<1,000 , D<1,000,000,000

(입력으로 주어지는 모든 수가 1이상 10억 미만임이 보장된다.)

Output
comet이 D일 후에 0번째 칸에 도착할 수 있는 경우의 수를 출력한다.

IO Example
입력1

5 2 3

출력1

3


입력2

10 1 2

출력2

0