← 返回题目列表

AtCoder · abc205_e

E. 白球和黑球

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有多少种排列方式 N 白球和 M 黑球从左到右连续满足以下条件?

  • 对于每个 i (1 \leq i \leq N + M),让 w_i 和 b_i 是最左边的白球和黑球的数量 分别为 i 球。然后, w_i \leq b_i + K 对于每个都成立 i.

由于计数可能很大,请对它求模 (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

有 10 安排方式 2 白球和 3 黑球连续,如下图,其中 w 和 b 分别代表白球和黑球。

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

其中, wwbbb 是唯一一个不满足条件的。这里,有 2 白球和 0 黑球之中 2 最左边的球,我们有 2 > 0 + K = 1.


示例输入 2

1 0 0

示例输出 2

0

可能无法满足该条件。


示例输入 3

1000000 1000000 1000000

示例输出 3

192151600

请务必打印模数计数 (10^9 + 7).