E. Максимум в массиве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Петя решал очень интересную задачу. Однако, какие бы оптимизации Петя ни применял, его решение всё равно получало вердикт Time limit exceeded. После тщательного анализа кода он обнаружил, что проблема заключается в его функции поиска максимума в массиве из n положительных чисел, которая работала слишком долго. В отчаянии Петя решил добавить весьма неожиданное отсечение с параметром 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 последовательных итераций этот максимум не изменился, то текущий максимум возвращается как ответ.

Теперь Пете стало интересно, как часто его функция даёт неверный ответ. Он просит вас посчитать количество перестановок чисел от 1 до n таких, что результат работы его функции на этих перестановках не равен n. Так как ответ может быть большим, выведите его по модулю 109 + 7.

Входные данные

В единственной строке находятся два целых числа n и k (1 ≤ n, k ≤ 106), разделённые пробелом — размер перестановок и параметр k соответственно.

Выходные данные

Выведите количество перестановок, на которых функция Пети выдаёт неправильный ответ, взятое по модулю 109 + 7.

Примеры
Входные данные
5 2
Выходные данные
22
Входные данные
5 3
Выходные данные
6
Входные данные
6 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].