HILO (Платина)

Бесі знає число x + 0.5, де $x$ — це деяке ціле число від $0$ до $n$, включно.

Ельза намагається вгадати це число. Вона може ставити питання виду "чи $i$ більше чи менше?" для деякого $i$ від $1$ до $n$ включно. Бесі відповідає "HI!", якщо $i$ більше ніж x + 0.5, і "LO!", якщо $i$ менше ніж x + 0.5.

Ельза дотримується наступної стратегії. Вона створила список з $n$ чисел, де кожне число від $1$ до $n$ зустрічається рівно один раз (іншими словами, цей список є перестановкою розміру $n$). Потім вона йде по цьому списку, називаючи числа для вгадування з нього по порядку. Однак вона пропускає всі непотрібні запити. Тобто, якщо Ельза повинна спитати число $i$, а раніше вона питала число j < i таке, що Бесі відповіла "HI!", Ельза не питає $i$, а переходить до наступного числа в списку. Аналогічно, якщо вона раніше питала про число j > i, на яке Бесі відповіла "LO!", Ельза також пропускає це число $i$ і переходить до наступного в списку. Можна довести, що використовуючи цю стратегію, Ельза завжди унікально визначить $x$ незалежно від перестановки, яку вона створить.

Якщо ми об'єднаємо всі відповіді Бесі "HI" або "LO" в один рядок $s$, кількість разів, коли Бесі відповість "HILO", є кількістю підрядків довжини $4$ в рядку $s$, які дорівнюють "HILO".

Бесі знає, що Ельза використовує цю стратегію і навіть вже вибрала число $x$, однак вона не знає, яку перестановку використовує Ельза. Ваше завдання — обчислити суму кількостей разів, які Бесі скаже "HILO" для всіх перестановок, які Ельза може використовувати — по модулю 10^9 + 7.