Задача . E. Медуза и взлом

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

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\).