問題一覧 > 通常問題

No.823 Many Shifts Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 118
作問者 : PulmnPulmn / テスター : e869120e869120
4 ProblemId : 2446 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-26 23:41:05

問題文

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