EOJ Monthly 2021.1 Sponsored by TuSimple

D. 区间替换

单点时限: 2.0 sec

内存限制: 512 MB

Cuber QQ 有一个数组 $[a_1, a_2, \cdots, a_n]$,一开始全为 $0$。

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

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

输入格式

一行两个整数 $n, m$($1 \le m \le n \le 10^6$)。

输出格式

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

样例

Input
4 2
Output
4
Input
7 3
Output
25
Input
15 4
Output
8500

提示

对于样例一,合法的数组为:

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

对于样例二,其中一些合法的数组为:

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