No.824 Many Shifts Hard
Problem Statement
There are $N+1$ squares arranged in a horizontal row, numbered $0,1,\dots,N$ from left to right. Also, on each of squares $1$ through $N$, $1$ piece is placed.
Here, for a sequence $A$ of length $K$ consisting of integers between $1$ and $N$, inclusive, define its score as the sum of the numbers of the squares on which $1$ or more pieces are placed after performing the following operation.
Operation: For $i=1,2,\dots,K$ in this order, move all pieces on square $A_i$ to square $A_i-1$.
There are $N^K$ sequences of length $K$ consisting of integers between $1$ and $N$, inclusive.
Compute the score for every sequence, and find the sum of the scores modulo $10^9+7$.
Input
$N$ $K$
$1\le N\le 10^5$
$1\le K\le 300$
Output
Output the sum of the scores over all sequences, modulo $10^9+7$. Print a newline at the end.
Sample
Sample 1
Input
6 4
Output
15110
Consider the case $A=(6,6,5,1)$.
$i=1$: Square $6$ has $1$ piece on it, and that piece is moved to square $5$.
$i=2$: Square $6$ has no pieces on it, so nothing changes.
$i=3$: Square $5$ has $2$ pieces on it, and those pieces are moved to square $4$.
$i=4$: Square $1$ has $1$ piece on it, and that piece is moved to square $0$.
In the end, squares $0,2,3,4$ have $1$ or more pieces on them, so the score of the sequence $A=\{6,6,5,1\}$ is $0+2+3+4=9$.
Sample 2
Input
1 1
Output
0
Sample 3
Input
1000 100
Output
489487189
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Pulmn
e869120