该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：move.in 输出文件：move.out

有 \(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$\) 种。

输入格式

一行，两个整数 $N$ 和 $K$。

输出格式

一个整数，表示所有 $N^K$ 个序列对应的得分之和对 \(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

数据范围

对于 10% 的数据，$N=1$。

对于 20% 的数据，$N \le 30$。

对于 35% 的数据，$N \le 400$。

另有 5% 的数据，$K=1$。

对于 100% 的数据，$1 \le N \le 10^5$，$1 \le K \le 300$。