配点 : $500$ 点

問題文

白いボール $N$ 個と黒いボール $M$ 個を横一列に並べる方法であって、次の条件を満たすものは何通りありますか？

• 各 $i \, (1 \leq i \leq N + M)$ について左から $i$ 個のボールのうち白いものの個数を $w_i$、黒いものの個数を $b_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)$ で割ったあまりを求めることに注意すること。

2 3 1

9

白いボール $2$ 個と黒いボール $3$ 個を並べる方法は $10$ 通りあり、白いボールを w、黒いボールを b で表すと以下のようになります。

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

このうち、条件を満たさないのは wwbbb のみです。左から $2$ 個のボールのうち白いものは $2$ 個、黒いものは $0$ 個ありますが、$2 > 0 + K = 1$ となっています。

1 0 0

0

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

1000000 1000000 1000000

192151600

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