No.824 Many Shifts Hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 12
作問者 : PulmnPulmn / テスター : e869120e869120
0 ProblemId : 2449 / 出題時の順位表

問題文

$N+1$ 個のマスが横一列に並んでいて、左から順に $0,1,\dots,N$ と番号が振られています。また、$1$ 番目から $N$ 番目の各マスに $1$ つずつ駒が置かれています。
ここで、長さ $K$ の $1$ 以上 $N$ 以下の整数列 $A$ の得点を、次の操作を行った後の駒が $1$ 個以上置かれているマスの番号の総和 と定義します。

操作:$i=1,2,\dots,K$ の順番に $A_i$ 番目のマスにある全ての駒を $A_i-1$ 番目のマスに移す

長さ $K$ の $1$ 以上 $N$ 以下の整数列は $N^K$ 通りあります。
全ての整数列について得点を調べて、その総和を $10^9+7$ で割ったときの余りを求めてください。

入力

$N$ $K$

$1\le N\le 10^5$
$1\le K\le 300$

出力

全ての整数列における得点の総和を $10^9+7$ で割ったときの余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
6 4
出力
15110

$A=(6,6,5,1)$ の場合

$i=1$:$6$ 番目のマスには駒が $1$ つ置かれており、その駒を $5$ 番目のマスに移す
$i=2$:$6$ 番目のマスには駒が置かれていないので変化なし
$i=3$:$5$ 番目のマスには駒が $2$ つ置かれており、その駒を $4$ 番目のマスに移す
$i=4$:$1$ 番目のマスには駒が $1$ つ置かれており、その駒を $0$ 番目のマスに移す

最終的に、$0,2,3,4$ 番目のマスに $1$ つ以上の駒が置かれているので、整数列 $A=\{6,6,5,1\}$ の得点は $0+2+3+4=9$

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

サンプル3
入力
1000 100
出力
489487189

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。