题目描述

白いボール $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)$ で割ったあまりを求めることに注意すること。

题目大意

给出 $n$ 个白球，$m$ 个黑球及一个常数 $k$，问有多少种排列使得 $\forall i\in[1,n+m],w_i\le b_i+k$，其中 $w_i$ 表示在排列的第 $i$ 个球以及它之前的白球个数，$b_i$ 表示在排列的第 $i$ 个球以及它之前的黑球个数。

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$
• 入力は全て整数である。

Sample Explanation 1

白いボール $2$ 個と黒いボール $3$ 個を並べる方法は $10$ 通りあり、白いボールを w、黒いボールを b で表すと以下のようになります。 wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww このうち、条件を満たさないのは wwbbb のみです。左から $2$ 個のボールのうち白いものは $2$ 個、黒いものは $0$ 個ありますが、$2\ >\ 0\ +\ K\ =\ 1$ となっています。

Sample Explanation 2

条件を満たす並べ方が存在しないこともあります。

Sample Explanation 3

$(10^9\ +\ 7)$ で割ったあまりを出力することに注意してください。