JDCC '16 Contest 3 P5 - CPT Elections

View as PDF

Submit solution


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é.


Comments

There are no comments at the moment.