← 返回题目列表

Codeforces · 886/E

E. 最大元素

中文机器翻译题面 查看原题

有一天,Petya 正在解决一个非常有趣的问题。但尽管他使用了很多优化技术,他的解决方案仍然得到了超出时间限制的判决。 Petya 对他的程序进行了彻底的分析,发现他在 n 个正整数数组中查找最大元素的函数太慢了。绝望之下,Petya 决定使用参数 k 使用一种有点出乎意料的优化,所以现在他的函数包含以下代码:

这样,函数会迭代检查数组元素,存储中间最大值,如果在连续 k 次迭代后该最大值没有改变,则将其作为答案返回。

现在 Petya 对他的函数的错误率感兴趣。他要求你找出从 1 到 n 的整数排列数,使得他的函数在这些排列上的返回值不等于 n。由于这个数字可能非常大,因此输出对 109 + 7 求模的结果。

输入

唯一的一行包含两个整数 n 和 k (1 ≤ n, k ≤ 106),用空格分隔 - 排列的长度和参数 k。

输出

输出对 109 + 7 求模的问题的答案。

示例

输入 #1

5 2

输出 #1

22

输入 #2

5 3

输出 #2

6

输入 #3

6 3

输出 #3

84

注意

第二个示例的排列:

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