Batman has got hold of Falcone and now needs to find all the criminals working under Falcone. Falcone tells Batman that all they is an infinite network of criminals and there are k criminals working under each criminal such that each criminal has a crime level of k units. Note that the crime level is shown by the edges in the network.

This means that the criminal network is a infinite rooted tree with each node having exactly k children nodes. Each edge has some weight. Also, if we look at the edges that goes from the vertex to its children (exactly k edges), then their weights will equal 1, 2, 3,..., k.

Now, Batman wondered: "How many criminals of total crime level n (the sum of all weights of the edges of the path) are there, starting the root of the tree and also containing at least one criminal of crime level at least d?".

That is, how many paths of total sum n (sum of all the crime levels in that path) are there, starting from the root of the tree and also containing at least one edge of weight at least d?. Note that there is one path for reaching the top most criminal (with no weight, n=0).

Here is a part of a sample tree with k = 3.

Input

A single line contains three spaced-seperated integers: n, k and d (1 <= n, k <= 100, 1 <= d <= k).

Output

Output a single integer - the solution to problem modulo 10^9 + 7.