AtCoder Grand Contest 070
翻译中…
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.
翻译中…
样例
Input #1
5 2 2
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.
Input #2
70 29 12
Output #2
693209192
Remember to find the count modulo $(10^9 + 7)$.
Input #3
20000000 1234567 890123
Output #3
566226457
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。