E - White and Black Balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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) で割ったあまりを求めることに注意すること。

入力例 1

2 3 1

出力例 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 となっています。

入力例 2

1 0 0

出力例 2

0

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

入力例 3

1000000 1000000 1000000

出力例 3

192151600

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

Score : 500 points

Problem Statement

How many ways are there to arrange N white balls and M black balls in a row from left to right to satisfy the following condition?

  • For each i (1 \leq i \leq N + M), let w_i and b_i be the number of white balls and black balls among the leftmost i balls, respectively. Then, w_i \leq b_i + K holds for every i.

Since the count can be enormous, find it modulo (10^9 + 7).

Constraints

  • 0 \leq N, M \leq 10^6
  • 1 \leq N + M
  • 0 \leq K \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer. Be sure to find the count modulo (10^9 + 7).

Sample Input 1

2 3 1

Sample Output 1

9

There are 10 ways to arrange 2 white balls and 3 black balls in a row, as shown below, where w and b stand for a white ball and a black ball, respectively.

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

Among them, wwbbb is the only one that does not satisfy the condition. Here, there are 2 white balls and 0 black balls among the 2 leftmost balls, and we have 2 > 0 + K = 1.

Sample Input 2

1 0 0

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

1000000 1000000 1000000

Sample Output 3

192151600

Be sure to print the count modulo (10^9 + 7).