No.1518 Simple Combinatorics
タグ : / 解いたユーザー数 137
作問者 :
NatsubiSogan
/ テスター :
aspi
soraie_
👑 
Nachia
問題文
正の整数 $N,K$ が与えられます。
あなたは、以下の操作をちょうど $K$ 回繰り返します。
- $1$ 以上 $N$ 以下の整数を一様ランダムに選ぶ（この選択は他の操作とは独立である）。選んだ整数をノートに記入する。
操作終了後のノートに書かれている整数の種類数の期待値に $N^K$ を掛けた値（これは整数になることが示せます）を $10^9+7$ （素数）で割った余りを出力してください。
入力
$N\ K$
- 入力はすべて整数
- $1 \leq N,K \lt 10^9+7$
出力
求めた期待値に $N^K$ を掛けた値を $10^9+7$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 3
出力
14
$1$ しか出ない場合が $1$ 通り、$2$ しか出ない場合も $1$ 通り、両方が出る場合は $6$ 通り考えられるので、期待値は $\displaystyle \frac{1 \times 2 + 2 \times 6}{2^3} = \frac{14}{8}$ であり、これに $2^3 = 8$ を掛けた $14$ が答えです。
サンプル2
入力
1 100
出力
1
$1$ 以外選ばれようがありません。
サンプル3
入力
314159265 358979323
出力
733723634
求めた答えを $10^9+7$ で割った余りを答えることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。