CF886E.Maximum Element

One day Petya was solving a very interesting problem. But although he used many optimization techniques, his solution still got Time limit exceeded verdict. Petya conducted a thorough analysis of his program and found out that his function for finding maximum element in an array of n positive integers was too slow. Desperate, Petya decided to use a somewhat unexpected optimization using parameter k, so now his function contains the following code:

int fast_max(int n, int a[]) {
int ans = 0;
int offset = 0;
for (int i = 0; i < n; ++i)
if (ans < a[i]) {
ans = a[i];
offset = 0;
} else {
offset = offset + 1;
if (offset == k)
return ans;
}
return ans;
}

That way the function iteratively checks array elements, storing the intermediate maximum, and if after k consecutive iterations that maximum has not changed, it is returned as the answer.

Now Petya is interested in fault rate of his function. He asked you to find the number of permutations of integers from 1 to n such that the return value of his function on those permutations is not equal to n. Since this number could be very big, output the answer modulo 109 + 7.

有一天，Petya 正在解决一个非常有趣的问题。但尽管他使用了许多优化技巧，他的程序仍然收到了“超出时间限制”的判决。Petya 对自己的程序进行了彻底分析，发现他在长度为 $n$ 的正整数数组中查找最大元素的函数运行得太慢了。绝望之下，Petya 决定采用一种略显出人意料的、基于参数 $k$ 的优化方式；于是，他的函数现在包含如下代码：

int fast_max(int n, int a[]) {   
    int ans = 0;  
    int offset = 0;  
    for (int i = 0; i < n; ++i)  
        if (ans < a[i]) {  
            ans = a[i];  
            offset = 0;  
        } else {  
            offset = offset + 1;  
            if (offset == k)  
                return ans;  
        }  
    return ans;  
}

该函数以迭代方式遍历数组元素，维护当前遇到的最大值；若连续 $k$ 次迭代中该最大值均未更新，则立即将其作为答案返回。

现在 Petya 关心的是该函数的错误率。他请你计算：在 $1$ 到 $n$ 的所有排列中，有多少个排列使得该函数的返回值不等于 $n$？由于结果可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

The only line contains two integers n and k (1 ≤ n, k ≤ 106), separated by a space — the length of the permutations and the parameter k.

单行包含两个整数 $n$ 和 $k$（$1 ≤ n, k ≤ 10^6$），以空格分隔——分别表示排列的长度和参数 $k$。

Output the answer to the problem modulo 109 + 7.

将问题的答案对 $10^9 + 7$ 取模后输出。

Permutations from second example:

[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].

第二个样例中的排列：

[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]。