白球与黑球

题目描述

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

对于每个 $i$（$1 \le i \le N+M$），设最左侧的 $i$ 个球中白球和黑球的个数分别为 $w_i$ 和 $b_i$。要求对每个 $i$ 都满足 $w_i \le b_i + K$。

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

输入格式

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

$N$ $M$ $K$

输出格式

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

样例

2 3 1

9

将 2 个白球和 3 个黑球排成一排共有 10 种方式，如下所示（w 表示白球，b 表示黑球）：

wwbbb
wbwbb
wbbwb
wbbbw
bwwbb
bwbwb
bwbbw
bbwwb
bbwbw
bbbww

其中只有 wwbbb 不满足条件。此时最左侧的 2 个球中白球有 2 个、黑球有 0 个，且 $2 \gt 0+K=1$。

1 0 0

0

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

1000000 1000000 1000000

192151600

请务必输出对 $(10^9+7)$ 取模后的结果。

数据范围

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