/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
Alice と Bob はじゃんけんを N 回行いました。
1 回のじゃんけんの結果は「Alice の勝ち」「Bob の勝ち」「引き分け」のいずれかです。
以下の条件を満たす N 回のじゃんけんの結果は何通りありますか？答えを \bf{1000000007 = 10^9 + 7} で割った余りを求めてください。
- N 回のうち Alice が勝ったのは A 回、Bob が勝ったのは B 回だった。
- Alice が引き分けを挟まずに 2 連続で勝つことはなかった。
- Bob が引き分けを挟まずに 2 連続で勝つことはなかった。
- どの時点においても Alice の勝利数が Bob の勝利数を下回ることはなかった。形式的に説明すると、1 \leq i \leq N を満たす i 全てに対して、「じゃんけんが i 回終了した時点での Alice の勝利数」は「じゃんけんが i 回終了した時点での Bob の勝利数」以上だった。
制約
- 2 \leq N \leq 2 \times 10^7
- 1 \leq B \leq A
- A + B \leq N
- N, A, B は整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
条件を満たす N 回のじゃんけんの結果の個数を 10^9 + 7 で割った余りを求めよ。
入力例 1
5 2 2
出力例 1
5
例えば、次の N 回のじゃんけんの結果は問題文の条件を満たします。
- 1 回目のじゃんけんで Alice が勝つ。
- 2 回目のじゃんけんで Bob が勝つ。
- 3 回目のじゃんけんで Alice が勝つ。
- 4 回目のじゃんけんで両者が引き分ける。
- 5 回目のじゃんけんで Bob が勝つ。
一方、次の N 回のじゃんけんの結果は 問題文の条件を満たしません。なぜならば、4 回目のじゃんけんが終了した時点で Alice の勝利数 (= 1) が Bob の勝利数 (= 2) を下回っているからです。
- 1 回目のじゃんけんで Alice が勝つ。
- 2 回目のじゃんけんで Bob が勝つ。
- 3 回目のじゃんけんで両者が引き分ける。
- 4 回目のじゃんけんで Bob が勝つ。
- 5 回目のじゃんけんで Alice が勝つ。
問題文の条件を満たす結果は全部で 5 通りあります。
入力例 2
70 29 12
出力例 2
693209192
個数を 10^9 + 7 で割った余りを求める点に注意してください。
入力例 3
20000000 1234567 890123
出力例 3
566226457
Score : 1000 points
Problem Statement
Alice and Bob played rock-paper-scissors N times.
Each round of rock-paper-scissors results in “Alice’s win,” “Bob’s win,” or “Draw.”
Among all possible sequences of results of N rounds, how many satisfy the following conditions? Find the count modulo \bf{1000000007 = 10^9 + 7}.
- Among the N rounds, Alice won exactly A times and Bob won exactly B times.
- Alice never won twice in a row without intervening draws.
- Bob never won twice in a row without intervening draws.
- At no point did Bob’s number of wins exceed Alice’s number of wins. Formally, for all 1 \leq i \leq N, “the number of times Alice has won up through round i” is at least “the number of times Bob has won up through round i.”
Constraints
- 2 \leq N \leq 2 \times 10^7
- 1 \leq B \leq A
- A + B \leq N
- N, A, and B are integers.
Input
The input is given from Standard Input in the following format:
N A B
Output
Print the number, modulo (10^9 + 7), of sequences of results of N rounds that satisfy the conditions.
Sample Input 1
5 2 2
Sample Output 1
5
For example, the following sequence of N rounds satisfies the conditions:
- Round 1: Alice wins.
- Round 2: Bob wins.
- Round 3: Alice wins.
- Round 4: Draw.
- Round 5: Bob wins.
On the other hand, the following sequence of N rounds does not satisfy the conditions, because after round 4, Alice’s number of wins (=1) is less than Bob’s number of wins (=2):
- Round 1: Alice wins.
- Round 2: Bob wins.
- Round 3: Draw.
- Round 4: Bob wins.
- Round 5: Alice wins.
There are five sequences in total that satisfy the conditions.
Sample Input 2
70 29 12
Sample Output 2
693209192
Remember to find the count modulo (10^9 + 7).
Sample Input 3
20000000 1234567 890123
Sample Output 3
566226457