AT_abc205_e [ABC205E] White and Black Balls

题目描述

有 $N$ 个白球和 $M$ 个黑球，将它们排成一行，有多少种排列方式满足以下条件：

• 对于每个 $i\ (1 \leq i \leq N + M)$，设从左起前 $i$ 个球中白球的个数为 $w_i$，黑球的个数为 $b_i$，则对于所有的 $i$ 都有 $w_i \leq b_i + K$。

由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

输入为一行，包含三个整数：

$N$ $M$ $K$

输出格式

输出满足条件的排列方式数，对 $10^9 + 7$ 取模。

样例 1

输入

2 3 1

输出

9

样例 2

输入

1 0 0

输出

0

样例 3

输入

1000000 1000000 1000000

输出

192151600

说明/提示

限制条件

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

样例解释 1

将 $2$ 个白球和 $3$ 个黑球排列的方法共有 $10$ 种，用 w 表示白球，b 表示黑球，排列如下：
wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww
其中不满足条件的是 wwbbb，因为从左起前 $2$ 个球中白球有 $2$ 个，黑球有 $0$ 个，$2 > 0 + K = 1$。

样例解释 2

也可能不存在满足条件的排列方式。

样例解释 3

请注意输出答案时要对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译