题目描述

有 $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$ 取模。

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$
• 输入均为整数。

样例解释 1

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