分数: 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