問題一覧 > 通常問題

No.824 Many Shifts Hard

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : Pulmn / テスター : e869120
お気に入りにしたユーザー ProblemId : 2449 / 自分の提出
問題文最終更新日: 2019-04-26 23:41:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 212 (順位表) の他の問題:

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