## JDCC '16 Contest 3 P5 - CPT Elections

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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 \le M < N \le 10^6,\ 0 \le K \le N - M)$$.

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

#### Output

For each test case, output the number of ways the voting could have played out, modulo $$10^9+7$$.

#### Sample Input

2 1 0

#### Sample Output

2

#### Sample Input

6 5 0

#### Sample Output

132

#### Sample Input

11 8 1

#### Sample Output

11934

#### Explanation for Sample Input

In the first case, 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é.