White and Black Balls

题目描述

有多少种方法将 $N$ 个白球和 $M$ 个黑球从左到右排成一行，使其满足以下条件？

对于每个 $i$ $(1 \leq i \leq N + M)$，设 $w_i$ 和 $b_i$ 分别为最左边 $i$ 个球中白球和黑球的个数。则对于每个 $i$，都有 $w_i \leq b_i + K$ 成立。

由于计数可能非常大，请对 $(10^9 + 7)$ 取模后给出结果。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $K$

输出格式

输出答案。请务必对 $(10^9 + 7)$ 取模。

2 3 1

9

1 0 0

0

1000000 1000000 1000000

192151600

提示

$0 \leq N, M \leq 10^6$ $1 \leq N + M$ $0 \leq K \leq N$ 输入中的所有数值均为整数。把 $2$ 个白球和 $3$ 个黑球排成一行共有 $10$ 种方法，如下所示，其中 $w$ 和 $b$ 分别表示白球和黑球。 $wwbbb$ $wbwbb$ $wbbwb$ $wbbbw$ $bwwbb$ $bwbwb$ $bwbbw$ $bbwwb$ $bbwbw$ $bbbww$ 在这些排列中，只有 $wwbbb$ 不满足该条件。在最左边的 $2$ 个球中有 $2$ 个白球和 $0$ 个黑球，所以 2 > 0 + K = 1.
也可能不存在满足条件的排列。
请务必对 $(10^9 + 7)$ 取模后输出计数。

标签: AtCoder|abc205E

来源

AtCoder|abc205E