有一天,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].