No.824 Many Shifts Hard
タグ : / 解いたユーザー数 20
作問者 :
Pulmn
/ テスター :
e869120
問題文
$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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。