Yet Another Expected Value

AtCoder

IDarc180_f

Time2000ms

Memory256MB

Difficulty—

You are given integers $N$ and $A$. You will perform the following operations: * Generate $N$ real numbers uniformly at random between $0$ and $1$, inclusive. All generations are independent, and the random numbers are uniformly distributed. * Call the generated $N$ real numbers $x_1, x_2, \cdots, x_N$ in ascending order. That is, $0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq 1$. * Your score is given by the following formula: $\displaystyle \prod_{i=1}^{N} \left(1+\sum_{j=i+1}^N x_j^A \right)$ Calculate the expected value, modulo $10^9+7$, of the score. Definition of expected value modulo $10^9+7$It can be proved that the sought expected value is always rational. Furthermore, under the constraints of this problem, it can be proved that if the expected value is expressed as an irreducible fraction $\frac{P}{Q}$, then $Q \neq 0 \pmod{10^9+7}$. Therefore, there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{10^9+7}, 0 \leq R < 10^9+7$. Report this $R$. ## Constraints * $1 \leq N \leq 10^4$ * $1 \leq A \leq 5 \times 10^4$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A$ [samples]

Samples

Input #1

2 1

Output #1

666666673

The expected value of the score is $5/3$.

Input #2

1 1

Output #2

Input #3

2 2

Output #3

500000005

Input #4

3 2

Output #4

142857147

Input #5

5 3

Output #5

758371066

Input #6

10000 12345

Output #6

32201773

API Response (JSON)

{
  "problem": {
    "name": "Yet Another Expected Value",
    "description": {
      "content": "You are given integers $N$ and $A$. You will perform the following operations: *   Generate $N$ real numbers uniformly at random between $0$ and $1$, inclusive. All generations are independent, and t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc180_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $N$ and $A$.\nYou will perform the following operations:\n\n*   Generate $N$ real numbers uniformly at random between $0$ and $1$, inclusive. All generations are independent, and t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments