# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.# Problem

André and Bertrand are campaigning to become the new CPT president. After a long campaign André was able to quench victory, receiving N votes to Bertrand’s M votes.

Reyno noticed that as the votes were tallied, an interesting pattern emerged. André received the first K votes and at every point of the tally, he was at least K votes ahead of Bertrand.

Reyno, always a fan of enumeration, wondered to himself: in how many ways could the tally have played out such that the above condition holds? Rather than solving it himself, he has enlisted your help. Don’t let him down!

# Input

Each test case contains three integers N, M, K (1 \leq M < N \leq 10^6, 0 \leq K \leq N - M).

For 70\% of the cases, N \leq 1,000.

# Output

For each test case, output the number of ways the voting could have played out, modulo 1,000,000,007.

# Sample Input 1

# Sample Output 1

# Sample Input 2

# Sample Output 2

# Sample Input 3

# Sample Output 3

# Explanation of Sample Output 1

The two ways the vote could have went is ABA and AAB, where A is a vote for André and B is a vote for Bertrand. BAA is not a valid since after the first vote, Bertrand has more votes than André.

# Editorial

not here yet