Problem 1057 --H.模糊最大值

1057: H.模糊最大值

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 13  Solved: 2
[Submit][Status][Web Board][Creator:]

Description

Alice的好朋友Bob最近致力于研究模糊算法的命中情况。现在他正在研究一种简单的模糊算法:模糊最大值。


	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;
}

       Bob决定研究1~n组成的全排列在这种算法下的命中情况。现在给定一个n以及k,请你求出有多少种排列方式,使得套用以上算法得出的模糊最大值不等于n。考虑到结果会非常大,请输出模109 + 7的结果。


Input

输入两个整数n 和k (1 ≤ n, k ≤ 106)。

Output

输出模109 + 7后的结果。

Sample Input

5 2
5 3
6 3

Sample Output

22
6
84

HINT


对于第二种样例,非命中的情况有:


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

Source

[Submit][Status]