← 返回题目列表

AtCoder · agc070_c

C. 无条纹

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

分数: 1000 点

问题陈述

爱丽丝和鲍勃玩石头剪刀布 N 次。 每轮石头剪刀布的结果都是“爱丽丝获胜”、“鲍勃获胜”或“平局”。
在所有可能的结果序列中 N 轮,有多少满足以下条件?求计数模数 \bf{1000000007 = 10^9 + 7}.

  • 其中 N 回合,Alice 完全获胜 A 次,鲍勃恰好获胜 B 次。
  • Alice 从未在没有抽奖的情况下连续两次获胜。
  • 鲍勃从未在没有抽签的情况下连续两次获胜。
  • Bob 的获胜次数从未超过 Alice 的获胜次数。正式地,对于所有 1 \leq i \leq N, “Alice 在一轮中获胜的次数 i”至少是“鲍勃在这一轮中获胜的次数 i.”

约束

  • 2 \leq N \leq 2 \times 10^7
  • 1 \leq B \leq A
  • A + B \leq N
  • N, A,和 B 是整数。

输入

输入由标准输入按以下格式给出:

N A B

输出

打印数字,模数 (10^9 + 7),结果序列 N 满足条件的回合。


示例输入 1

5 2 2

示例输出 1

5

例如,以下序列 N 轮次满足条件:

  • 圆形 1:爱丽丝获胜。
  • 圆形 2:鲍勃获胜。
  • 圆形 3:爱丽丝获胜。
  • 圆形 4:画画。
  • 圆形 5:鲍勃获胜。

另一方面,以下序列 N 轮确实 不 满足条件,因为经过一轮 4, Alice 的获胜次数 (=1) 小于 Bob 的获胜次数 (=2):

  • 圆形 1:爱丽丝获胜。
  • 圆形 2:鲍勃获胜。
  • 圆形 3:画画。
  • 圆形 4:鲍勃获胜。
  • 圆形 5:爱丽丝获胜。

满足条件的序列总共有5个。


示例输入 2

70 29 12

示例输出 2

693209192

记住求模数 (10^9 + 7).


示例输入 3

20000000 1234567 890123

示例输出 3

566226457