AT_abc205_e [ABC205E] White and Black Balls

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

### 制約 - $ 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) $ で割ったあまりを出力することに注意してください。