Rescue on the River

You are drifting on a river in a dream on a wooden boat. According to local knowledge, a deadly gorge lies exactly \(D\) meters downstream. If you ever drift \(D\) meters or more downstream, you will certainly perish.

You have managed to call for emergency help and the rescue team will arrive in \(T\) seconds. The river flows at a speed of \(1\,m/s\). You also have \(M\) energy points. Each energy point allows you to paddle for one second so that your boat moves \(1\,m\) upstream. If you do not paddle in a second, the boat is carried \(1\,m\) downstream by the current. Note that you must use exactly \(M\) energy points (i.e. paddle exactly \(M\) times) within \(T\) seconds. Since the river is too wide, you cannot reach the shore by paddling alone.

Your task is to determine the number of distinct paddle schedules that will allow you to be rescued. Two paddle schedules are considered different if there is at least one second where one schedule chooses to paddle while the other does not.

Important: At every second, let \(S_i\) denote your displacement (in meters) from the starting point (with downstream positive). A paddle gives \(-1\) change (upstream) and not paddling gives \(+1\) (downstream). To be rescued, the condition \[ S_i < D \quad \text{for all } 1 \le i \le T \] must be satisfied. In particular, if the final position \(S_T\) is \(\ge D\) you lose.

Hint: With exactly \(M\) paddles over \(T\) seconds, the final position is \(S_T=T-2M\). Using the reflection principle, the number of safe sequences is given by

[ \text{Answer} = \begin{cases} 0, & \text{if } T-2M \ge D,\ \binom{T}{M} - \binom{T}{T-M-D}, & \text{if } T-2M < D, \end{cases} ]

where by convention \(\binom{n}{k} = 0\) if \(k n\).

inputFormat

The input consists of a single line containing three space-separated integers \(D\), \(T\), and \(M\):

• \(D\) (the dangerous distance downstream)
• \(T\) (the total number of seconds before rescue arrives)
• \(M\) (the number of energy points, i.e. the number of paddles you must perform)

outputFormat

Output a single integer representing the number of paddle schedules that allow you to avoid drifting \(D\) meters or more downstream at any point. If no safe schedule exists, output 0.

sample

3 5 2

9