ESPers

AtCoder

IDagc053_f

Time3000ms

Memory256MB

Difficulty—

$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: 1. If everyone has already voted, the vote ends. Otherwise, proceed to step 2. 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). ## 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$ [samples] ## 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$.

Samples

Input #1

1 1

Output #1

916666674

X wins with probability $\frac{11}{12}$.

Input #2

1 2

Output #2

958333341

X wins with probability $\frac{23}{24}$.

Input #3

8 5

Output #3

582281799

Input #4

100 100

Output #4

196654831

Input #5

2000000 2000000

Output #5

768385859

API Response (JSON)

{
  "problem": {
    "name": "ESPers",
    "description": {
      "content": "$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 w",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc053_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$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 w...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments