Phần Tử Lớn Nhất

Cho hàm "tìm phần tử lớn nhất" sau đây, được tham số hoá bởi một hằng số $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;
}

Hàm này duyệt mảng và duy trì giá trị lớn nhất hiện tại trong ans. Nếu trong $k$ vòng lặp liên tiếp giá trị ans không thay đổi thì hàm dừng sớm và trả về ans.

Cho hai số nguyên $n$ và $k$. Hãy đếm số hoán vị của $1,2,\dots ,n$ mà khi truyền vào hàm trên thì giá trị trả về không bằng $n$. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng chứa hai số nguyên $n$ và $k$ ($1\le n,k\le {10}^6$).

Dữ liệu ra

Một số nguyên — số hoán vị thoả mãn, modulo ${10}^9+7$.

Ràng buộc

• $1\le n,k\le {10}^6$.

Ví dụ