Перестановки

Для перестановки $p$ чисел від $1$ до $n$, визначимо $f(p)$ наступним чином: для кожної пари чисел $(i,j)$ з 1 \le i \le j \le n, порахуємо пару $(\min ,\max )$, де $\min$ — найменше число серед чисел p_i, p_{i+1}, \ldots, p_j, а $\max$ — найбільше з них. Тоді $f(p)$ дорівнює кількості різних пар серед усіх \frac{n(n+1)}{2} пар.

Наприклад, розглянемо перестановку (1, 3, 2).

• Для пари $(1,1)$, (\min, \max) = (1, 1)

• Для пари $(1,2)$, (\min, \max) = (1, 3)

• Для пари $(1,3)$, (\min, \max) = (1, 3)

• Для пари $(2,2)$, (\min, \max) = (3, 3)

• Для пари $(2,3)$, (\min, \max) = (2, 3)

• Для пари $(3,3)$, (\min, \max) = (2, 2)

Всього $5$ різних пар, тому f((1, 3, 2)) = 5.

Знайдіть суму $f(p)$ по всіх перестановках $p$ довжини $n$, за модулем 10^9 + 7.