/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 2400 点
問題文
2N+1 人の参加者で、多数決というゲームを行います。各参加者は 2 つの選択肢の一方に投票し、最終的により多くの票を集めた選択肢に投票した参加者が勝者となります。投票は具体的には以下のように行われます。
- 全員が投票を終えた場合、そこで投票は終了する。そうでない場合、2. に進む。
- 投票をしていない参加者のうち 1 人がランダムに選ばれ、その人が投票を行う。そして、1. に戻る。
参加者のうち K 人は超能力者であり、自身の投票時に、各選択肢が何票投票されているのかを知ることができます。 そのため、各参加者は以下のようにして投票先を決定します。
- 参加者が超能力者の場合、その時点でより多くの票を集めている選択肢に投票する。ただし、その時点で各選択肢の票数が等しい場合は、ランダムに一方の選択肢を選び投票する。
- 参加者が超能力者でない場合、ランダムに一方の選択肢を選び投票する。
X はこのゲームの参加者であり、超能力者でもあります。X の勝率を \bmod 10^9+7 で求めてください（注記参照）。
注記
- 求める確率は有理数となります。確率を分数 \frac{y}{x}（x と y は互いに素な正の整数）で表したとき、x は P=10^9+7 と互いに素になるので、 xz \equiv y \pmod P なる 0 以上 P-1 以下の唯一の整数 z を出力してください。
制約
- 1 \leq N \leq 2\times 10^6
- 1 \leq K \leq 2N+1
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを出力せよ。
入力例 1
1 1
出力例 1
916666674
X の勝率は \frac{11}{12} です。
入力例 2
1 2
出力例 2
958333341
X の勝率は \frac{23}{24} です。
入力例 3
8 5
出力例 3
582281799
入力例 4
100 100
出力例 4
196654831
入力例 5
2000000 2000000
出力例 5
768385859
Score : 2400 points
Problem Statement
2N+1 players will play a game called Majority Vote. Each player casts a vote to one of the two options given, and the players choosing the option that ends up with the greater number of votes will win. The detailed progression of the vote is as follows:
- If everyone has already voted, the vote ends. Otherwise, proceed to step 2.
- One player is chosen randomly among the players who have not voted, and s/he casts a vote. Then, go back to step 1.
K of the players are ESPers, who can know the number of votes cast to each option when they cast votes. Thus, the players choose the option to cast as follows:
- A player who is an ESPer chooses the option with the greater number of votes at the moment. If the two options have the same number of votes, s/he chooses one option randomly and votes for it.
- A player who is not an ESPer randomly chooses one option and votes for it.
X is a player of the game who is also an ESPer. Find the probability that X wins, modulo (10^9+7) (see Notes).
Notes
- The expected value in question will be a rational number. If we express it as a fractional number \frac{y}{x} where x and y are coprime positive integers, x will be coprime with P=10^9+7, so print the only integer z between 0 and P-1 (inclusive) such that xz \equiv y \pmod P.
Constraints
- 1 \leq N \leq 2\times 10^6
- 1 \leq K \leq 2N+1
Input
Input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
1 1
Sample Output 1
916666674
X wins with probability \frac{11}{12}.
Sample Input 2
1 2
Sample Output 2
958333341
X wins with probability \frac{23}{24}.
Sample Input 3
8 5
Sample Output 3
582281799
Sample Input 4
100 100
Sample Output 4
196654831
Sample Input 5
2000000 2000000
Sample Output 5
768385859