题目描述

oql 想知道，有多少个 $n$ 阶排列，满足：

• $\forall i\in[m+1,n],a_i>\min(a_{i-1},a_{i-2},\cdots,a_{i-m})$。

由于答案可能很大，输出答案对 $10^9+7$ 取模后的结果。

输入格式

一行两个整数 $n,m$。

输出格式

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

样例数据

样例输入

4 2

样例输出

10

数据范围

子任务一（ $20$ 分）：$n\le 10$。

子任务二（ $30$ 分）：$n\le 5000$。

子任务三（ $25$ 分）：$n\le 10^6$。

子任务四（ $25$ 分）：无特殊限制。

对于所有数据：$1\le m\le n \le 10^7$。