单点时限: 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$）。
一行一个整数，表示答案。
4 2
4
7 3
25
15 4
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}
$$