F - Yet Another Expected Value 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1100 点

問題文

整数 N,A が与えられます．

あなたはこれから以下の操作を行います．

  • 0 以上 1 以下の実数をランダムに N 個生成する． すべての生成は独立であり，かつ乱数は一様であるものとする．
  • 生成した N 個の実数を小さい順に x_1,x_2,\cdots,x_N と呼ぶ． つまり，0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq 1 である．
  • ここで，あなたのスコアは次の式の値になる．

\displaystyle \prod_{i=1}^{N} \left(1+\sum_{j=i+1}^N x_j^A \right)

スコアの期待値を \pmod{10^9+7} で求めてください．

期待値 \pmod{10^9+7} の定義

求める期待値は必ず有理数になることが証明できます．また，この問題の制約のもとでは，その値を既約分数 \frac{P}{Q} で表した時，Q \neq 0 \pmod{10^9+7} となることも証明できます． よって，R \times Q \equiv P \pmod{10^9+7}, 0 \leq R < 10^9+7 を満たす整数 R が一意に定まります． この R を答えてください．

制約

  • 1 \leq N \leq 10^4
  • 1 \leq A \leq 5 \times 10^4
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N A

出力

答えを出力せよ．

入力例 1

2 1

出力例 1

666666673

スコアの期待値は 5/3 です．

入力例 2

1 1

出力例 2

1

入力例 3

2 2

出力例 3

500000005

入力例 4

3 2

出力例 4

142857147

入力例 5

5 3

出力例 5

758371066

入力例 6

10000 12345

出力例 6

32201773

Score : 1100 points

Problem Statement

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

Output

Print the answer.

Sample Input 1

2 1

Sample Output 1

666666673

The expected value of the score is 5/3.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

2 2

Sample Output 3

500000005

Sample Input 4

3 2

Sample Output 4

142857147

Sample Input 5

5 3

Sample Output 5

758371066

Sample Input 6

10000 12345

Sample Output 6

32201773