Score : $500$ points

问题描述

有多少种方法可以将 $N$ 个白球和 $M$ 个黑球从左到右依次排列以满足以下条件？

• 对于每个 $i$ $(1 \leq i \leq N + M)$，令 $w_i$ 和 $b_i$ 分别表示最左边 $i$ 个球中白球和黑球的数量。则对于所有 $i$，有 $w_i \leq b_i + K$ 成立。

由于计数结果可能非常巨大，请在 $(10^9 + 7)$ 模数下求解。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

How many ways are there to arrange $N$ white balls and $M$ black balls in a row from left to right to satisfy the following condition?

• For each $i$ $(1 \leq i \leq N + M)$, let $w_i$ and $b_i$ be the number of white balls and black balls among the leftmost $i$ balls, respectively. Then, $w_i \leq b_i + K$ holds for every $i$.

Since the count can be enormous, find it modulo $(10^9 + 7)$.

Constraints

• $0 \leq N, M \leq 10^6$
• $1 \leq N + M$
• $0 \leq K \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$

Output

Print the answer. Be sure to find the count modulo $(10^9 + 7)$.

Sample Input 1

2 3 1

Sample Output 1

9

There are $10$ ways to arrange $2$ white balls and $3$ black balls in a row, as shown below, where w and b stand for a white ball and a black ball, respectively.

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

Among them, wwbbb is the only one that does not satisfy the condition. Here, there are $2$ white balls and $0$ black balls among the $2$ leftmost balls, and we have $2 > 0 + K = 1$.

Sample Input 2

1 0 0

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

1000000 1000000 1000000

Sample Output 3

192151600

Be sure to print the count modulo $(10^9 + 7)$.

update @ 2024/3/10 09:18:41