Problem #4042 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 512 MB

Cuber QQ 有一个数组 $[a_{1}, a_{2}, \dots, a_{n}]$ ，一开始全为 $0$ 。

你可以对数组进行任意多次操作。每次，你将选择一个长度为 $m$ 的区间，并把数组的这部分替换成 $[1, 2, \dots, m]$ 。操作完后，你要保证数组中不存在 $0$ 。

现在，Cuber QQ 想考考你：最终能得到多少种不同的数组呢？你只需要求出答案对 $10^{9} + 7$ 取模的结果。

一行两个整数 $n, m$ （ $1 \leq m \leq n \leq 10^{6}$ ）。

一行一个整数，表示答案。

Input

4 2

Output

Input

7 3

Output

Input

15 4

Output

对于样例一，合法的数组为：

$\begin{aligned} [1, 1, 1, 2] [1, 1, 2, 2] [1, 2, 1, 2] [1, 2, 2, 2] \end{aligned}$

对于样例二，其中一些合法的数组为：

$\begin{aligned} [1, 1, 1, 2, 3, 2, 3] [1, 2, 3, 2, 1, 2, 3] [1, 2, 3, 3, 2, 3, 3] \end{aligned}$

35 人解决，58 人已尝试。

40 份提交通过，共有 129 份提交。

5.0 EMB 奖励。

创建: 4 年，4 月前.

修改: 4 年，3 月前.

最后提交: 1 年，10 月前.

4042. 区间替换