問題一覧 > 通常問題

No.1518 Simple Combinatorics

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 100
作問者 : NatsubiSoganNatsubiSogan / テスター : aspiaspi soraie_soraie_ NachiaNachia
5 ProblemId : 5979 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-02 19:02:55

問題文

正の整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。