Maximum Element

어느 날 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번의 연속된 반복 동안 그 최댓값이 바뀌지 않으면 이를 정답으로 반환한다.

Now Petya는 자신의 함수의 오류율에 관심이 있다. 그는 1부터 n까지의 정수로 이루어진 순열 중, 그 순열에 대한 함수의 반환값이 n과 같지 않은 순열의 개수를 구해 달라고 요청했다. 이 수는 매우 클 수 있으므로, 답을 109 + 7로 나눈 나머지를 출력한다.

유일한 줄에 공백으로 구분된 두 정수 n와 k (1 ≤ n, k ≤ 106)가 주어진다. 이는 각각 순열의 길이와 매개변수 k이다.

문제의 답을 109 + 7로 나눈 나머지를 출력한다.

두 번째 예제의 순열:

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