Известно, что быстрая сортировка работает путем случайного выбора «разделяющего» элемента из массива и разбиения остальных элементов на два подмассива в зависимости от того, меньше они или больше разделяющего. Но Медуза считает, что выбор случайного элемента — это пустая трата времени, поэтому она всегда выбирает первый элемент в качестве разделяющего. Время, необходимое для выполнения ее кода, можно вычислить с помощью следующего псевдокода:

function fun(A)
    if A.length > 0
        пусть L[1 ... L.length] и R[1 ... R.length] будут новыми массивами
        L.length = R.length = 0
        for i = 2 to A.length
            if A[i] < A[1]
                L.length = L.length + 1
                L[L.length] = A[i]
            else
                R.length = R.length + 1
                R[R.length] = A[i]
        return A.length + fun(L) + fun(R)
    else
        return 0

Теперь вы хотите показать ей, что ее код работает медленно. Когда функция $$$\mathrm{fun(A)}$$$ будет больше или равна $$$lim$$$, ее код получит вердикт $$$\text{Time Limit Exceeded}$$$. Вы хотите узнать, сколько различных перестановок $$$P$$$ массива $$$[1, 2, \dots, n]$$$ удовлетворяет $$$\mathrm{fun(P)} \geq lim$$$. Поскольку ответ может быть большим, вам нужно найти ответ только по модулю $$$10^9+7$$$.