No.823 Many Shifts Easy
タグ : / 解いたユーザー数 118
作問者 :
Pulmn
/ テスター :
e869120
問題文
$N+1$ 個のマスが横一列に並んでいて、左から順に $0,1,\dots,N$ と番号が振られています。また、$1$ 番目から $N$ 番目の各マスに $1$ つずつ駒が置かれています。
ここで、長さ $K$ の $1$ 以上 $N$ 以下の $\large \textbf{各要素が互いに異なる}$ 整数列 $A$ の得点を、以下の操作を行った後の駒が $1$ 個以上置かれているマスの番号の総和 と定義します。
操作：$i=1,2,\dots,K$ の順番に $A_i$ 番目のマスにある全ての駒を $A_i-1$ 番目のマスに移す
長さ $K$ の $1$ 以上 $N$ 以下の $\large \textbf{各要素が互いに異なる}$ 整数列は ${}_N\mathrm {P}_ K$ 通りあります。
全ての $\large \textbf{各要素が互いに異なる}$ 整数列について得点を調べて、その総和を $10^9+7$ で割ったときの余りを求めてください。
入力
$N$ $K$
$1\le K\le N\le 10^5$
出力
全ての $\large \textbf{各要素が互いに異なる}$ 整数列における得点の総和を $10^9+7$ で割ったときの余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
6 4
出力
3600
$A=(2,1,5,4)$ の場合
$i=1$：$2$ 番目のマスには駒が $1$ つ置かれており、その駒を $1$ 番目のマスに移す
$i=2$：$1$ 番目のマスには駒が $2$ つ置かれており、その駒を $0$ 番目のマスに移す
$i=3$：$5$ 番目のマスには駒が $1$ つ置かれており、その駒を $4$ 番目のマスに移す
$i=4$：$4$ 番目のマスには駒が $2$ つ置かれており、その駒を $3$ 番目のマスに移す
最終的に、$0,3,6$ 番目のマスに $1$ つ以上の駒が置かれているので、順列 $A=\{2,3,1,4\}$ の得点は $0+3+6=9$
サンプル2
入力
1 1
出力
0
サンプル3
入力
1000 100
出力
45281982
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。