题目描述

有多少种方法可以将 $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)$ 取模。

示例输入1

2 3 1

示例输出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$。

示例输入2

1 0 0

示例输出2

0

可能没有满足条件的方式。

示例输入3

1000000 1000000 1000000

示例输出3

192151600

请务必对 $(10^9+7)$ 取模打印计数。