Description

有 $N$ 个白球和 $M$ 个黑球排成一排，下标从 $1$ 开始，其中：

• $w_i$ 表示 $1$ 到 $i$ $(1 \leq i \leq N + M)$ 的位置中，白球的总数。
• $b_i$ 表示 $1$ 到 $i$ $(1 \leq i \leq N + M)$ 的位置中，黑球的总数。

给定一个常数 $K$，请问有多少种排列方式满足以下条件：

• 对于每一个 $i$ $(1 \leq i \leq N + M)$， $w_i \leq b_i + K$。

答案可能很大，请将答案对 $(10^9 + 7)$ 取模。

Format

Input

一行，三个整数 $N, M, K$ $(0 \leq N, M \leq 10^6, 1 \leq N + M, 0 \leq K \leq N)$。

Output

输出一个整数，表示排列方式种类数对 $(10^9 + 7)$ 取模的结果。

Samples

2 3 1

9

Note

有 $10$ 种方法可以将 $2$ 个白色球和 $3$ 个黑色球排列成一行，如下所示，其中 $w$ 和 $b$ 分别代表白色球和黑色球：

$wwbbb,wbwbb,wbbwb,wbbbw,bwwbb$ $bwbwb,bwbbw,bbwwb,bbwbw,bbbww$

其中，$wwbbb$ 是唯一一个不满足条件的排列，因为最左边的两个球都为白球，此时 $2 > 0 + 1$。

1 0 0

0

1000000 1000000 1000000

192151600

Limitation

1s, 1024KiB for each test case.