[ABC205E] White and Black Balls
题意翻译
给出 $n$ 个白球，$m$ 个黑球及一个常数 $k$，问有多少种排列使得 $\forall i\in[1,n+m],w_i\le b_i+k$，其中 $w_i$ 表示在排列的第 $i$ 个球以及它之前的白球个数，$b_i$ 表示在排列的第 $i$ 个球以及它之前的黑球个数。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc205/tasks/abc205_e
白いボール $ 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) $ で割ったあまりを求めることに注意すること。
输入输出样例
输入样例 #1
2 3 1输出样例 #1
9输入样例 #2
1 0 0输出样例 #2
0输入样例 #3
1000000 1000000 1000000输出样例 #3
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) $ で割ったあまりを出力することに注意してください。