問題一覧 > 通常問題

No.1518 Simple Combinatorics

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 138
作問者 : NatsubiSogan / テスター : aspi soraie_ 👑 Nachia
6 ProblemId : 5979 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-03 15:17:16

問題文

正の整数 N,K が与えられます。

あなたは、以下の操作をちょうど K 回繰り返します。

  • 1 以上 N 以下の整数を一様ランダムに選ぶ（この選択は他の操作とは独立である）。選んだ整数をノートに記入する。

操作終了後のノートに書かれている整数の種類数の期待値に NK を掛けた値（これは整数になることが示せます）を 109+7 （素数）で割った余りを出力してください。

入力

N K

  • 入力はすべて整数
  • 1≤N,K<109+7

出力

求めた期待値に NK を掛けた値を 109+7 で割った余りを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2 3
出力
14

1 しか出ない場合が 1 通り、2 しか出ない場合も 1 通り、両方が出る場合は 6 通り考えられるので、期待値は 1×2+2×623=148 であり、これに 23=8 を掛けた 14 が答えです。

サンプル2
入力
1 100
出力
1

1 以外選ばれようがありません。

サンプル3
入力
314159265 358979323
出力
733723634

求めた答えを 109+7 で割った余りを答えることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。