题目描述

小明喜欢玩 $minecraft$ 并且热衷于挖矿，他非常喜欢钻石矿和金矿，同时他还是个欧皇，在一次挖矿的过程中，他很快就得到了 $n$ 个钻石和 $m$ 个金。现在小明想把他的收获排成一排陈列出来，但是他有强迫症，而且喜欢一个数字 $k$ 和金闪闪的物品。如果用 $a_i$ 表示排列第 $i$ 个位置以及它之前位置的钻石个数，$b_i$ 表示第 $i$ 个位置以及它之前位置的金的个数，他希望排出来的排列，对于任意一个位置 $\forall i\in[1,n+m]$ ，都有 $a_i \le b_i + k$ 。现在小明想知道，有多少种排列方式满足他的要求，答案对 $10^9 + 7$ 取模。

输入格式

第一行输入三个整数 $n,m,k$ 。

输出格式

输出题目要求的答案。

样例 #1

样例输入 #1

2 3 1

样例输出 #1

9

假设用 $a$ 表示钻石， $b$ 表示金，显然有 $10$ 种排列方式，其中 aabbb 是不满足条件的排列，此排列第二个位置不满足。

样例 #2

样例输入 #2

1 0 0

样例输出 #2

0

样例 #3

样例输入 #3

1000000 1000000 1000000

样例输出 #3

192151600

提示

数据范围

• $0\ \leq\ N,\ M\ \leq\ 10^6$
• $1\ \leq\ N\ +\ M$
• $0\ \leq\ K\ \leq\ N$