E - 白球和黑球

分数: $500$ 分

问题描述

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

• 对于每个 $i$ $(1 \leq i \leq N + M)$，设 $w_i$ 和 $b_i$ 分别是前 $i$ 个球中的白球和黑球的数量。则对于每个 $i$，都有 $w_i \leq b_i + K$。

由于计数可能非常庞大，对 $(10^9 + 7)$ 取模。

约束条件

• $0 \leq N, M \leq 10^6$
• $1 \leq N + M$
• $0 \leq K \leq N$
• 输入中的所有值均为整数。

输入

从标准输入中以以下格式给出：

$N$ $M$ $K$

输出

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

2 3 1

9

共有 $10$ 种将 $2$ 个白球和 $3$ 个黑球排成一行的方式，如下所示，其中 w 和 b 分别代表白球和黑球。

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

其中，wwbbb 是唯一一种不满足条件的方式。这里，前 $2$ 个球中有 $2$ 个白球和 $0$ 个黑球，我们有 $2 > 0 + K = 1$。

1 0 0

0

有可能无法满足条件。

1000000 1000000 1000000

192151600

务必对 $(10^9 + 7)$ 取模。