Problem Description

In a dream, you step onto a wooden boat and drift on a river.

Based on what you know about the area, you know there is a canyon $D$ meters downstream. If you move downstream by at least $D$ meters, you will definitely die.

Now you have called emergency services. After $T$ seconds, the rescue team will arrive and pull you ashore. The water flows at a speed of $1 \mathrm{~m} / \mathrm{s}$. You currently have $M$ stamina points. Each time you spend $1$ stamina point, you can row for one second and make the boat move $1 \mathrm{~m}$ upstream; otherwise, you will move $1 \mathrm{~m}$ downstream (because of the current). All $M$ stamina points must be used up before the rescue team arrives. Because the river is too wide, you cannot get ashore by your own strength.

How many different rowing plans can allow you to survive?

Two rowing plans are considered different if there exists some second such that one plan rows during that second while the other plan does not.

Input Format

One line contains three integers $D$, $T$, and $M$.

Output Format

Output one integer, the total number of plans that allow you to survive. The answer may be very large, so output the result modulo $1000000007$ (i.e., $10^9+7$).

1 6 3

5

Hint

For $50\%$ of the testdata, $1 \leq T \leq 350$.

For all testdata, $1 \leq T \leq 3000$, $1 \leq D \leq T$, $1 \leq M \leq 1500$.

Lanqiao Cup 2020, Round 3 Provincial Contest, AB Group, Problem I.

Translated by ChatGPT 5