题目描述

这一天，小 J 学习了如何求序列最大值。他发现了该算法的一个漏洞：如果该序列的最大值比较靠前，那么最大值之后的枚举过程将十分浪费时间。所以他想出了如下算法：

1. 先确定常数 $k$，然后从第一个元素开始依次枚举，同时记录当前最大值 $mx$；
2. 如果当前位置及以前的连续 $k$ 个元素都比当前最大值小，那么就退出枚举，即：令当前位置为 $i$，如果下标区间 $[i-k+1,i]$ 内的所有元素都小于 $mx$，就退出枚举；
3. 否则更新当前最大值 $mx$；
4. 如果当前位置不是序列末尾，则继续枚举，否则退出枚举。

小 J 想知道该算法的正确率如何，所以他向你提出如下问题：给你两个数 $n,k_0$，求有多少长为 $n$ 的排列 $p$ 在常数 $k=k_0$ 的情况下会得到错误答案，即 $mx\ne n$。由于答案可能很大，所以他只需要答案对 $10^9+7$ 取模后的结果。

输入格式

从文件 arisu.in 中读入数据。

第一行包含两个整数 $n,k_0$，分别表示排列长度与常数 $k$ 的值。

输出格式

输出到文件 arisu.out 中。

一行一个整数，表示会得到错误答案的排列个数，对 $10^9+7$ 取模。

样例 1 输入

5 3

样例 1 输出

6

样例 1 解释

有如下 $6$ 个排列满足条件：$(4,1,2,3,5)$、$(4,1,3,2,5)$、$(4,2,1,3,5)$、$(4,2,3,1,5)$、$(4,3,1,2,5)$、$(4,3,2,1,5)$。可以证明不存在其他排列满足条件。

样例 2 输入

5 2

样例 2 输出

22

样例 3 输入

6 3

样例 3 输出

84

样例 4

见选手目录下的 arisu4.in 与 arisu4.ans。

该样例满足子任务 $2$ 的限制。

样例 5

见选手目录下的 arisu5.in 与 arisu5.ans。

该样例满足子任务 $2$ 的限制。

样例 6

见选手目录下的 arisu6.in 与 arisu6.ans。

该样例满足子任务 $3$ 的限制。

样例 7

见选手目录下的 arisu7.in 与 arisu7.ans。

该样例满足子任务 $3$ 的限制。

数据范围

对于所有测试数据，保证：$1\le n,k\le10^6$。

本题评测方式为：不捆绑，同一子任务内的测试点分数大致相等，总分为所有通过的测试点的分数总和。更详细地，子任务 $1$ 中每个测试点 $1$ 分，子任务 $3$ 中每个测试点 $2$ 分，子任务 $2$ 中前 $8$ 个测试点每个 $3$ 分，后 $4$ 个测试点每个 $4$ 分。