Как-то раз Петя решал очень интересную задачу. Однако, какие бы оптимизации Петя ни применял, его решение всё равно получало вердикт 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. Так как ответ может быть большим, выведите его по модулю 10⁹ + 7.