Коли немає чим зайнятись, а вдома лише перестановка

Дана перестановка $(p_1,p_2,\dots ,p_n)$ чисел від $1$ до $n$.

З нею ви можете робити наступну операцію:

• Ви можете переставити місцями два сусідні елементи $p$. Ця операція займає рівно одну секунду.

За одну ітерацію ви робите наступне:

• Розглянемо перестановку $(q_1,q_2,\dots ,q_n)$, що знаходиться прямо перед $(p_1,p_2,\dots ,p_n)$ в лексикографічному порядку, тобто $q$ лексикографічно менша за $p$ і не існує жодної перестановки "між ними". Наприклад, для $p=(2,3,1)$ $q=(2,1,3)$, для $p=(3,1,2,4)$ $q=(2,4,3,1)$, а для $p=(1,4,2,3)$ $q=(1,3,4,2)$.

• Перетворимо перестановку $p$ в перестановку $q$, за мінімально можливу кількість операцій. Наприклад, щоб перетворити $(1,4,2,3)$ в $(1,3,4,2)$, потрібно мінімум $2$ операції: $(1,4,2,3)\to (1,4,3,2)\to (1,3,4,2)$.

Ви застосовуєте до отриманої перестановки $p$ дану ітерацію, поки вона не стане тотожною перестановкою (тобто рівною $(1,2,3,\dots ,n))$. Скільки часу це займе? Оскільки це число може бути дуже великим, виведіть його за модулем $10^9+7$.

Перестановка $p$ вважається лексикографічно меншою за перестановку $q$, якщо існує такий індекс $i$, що $p_j=q_j$ для всіх $j<i$, а також $p_i<q_i$.

Giriş verilənləri

Перший рядок містить єдине число $n$ ($1\le n\le 2\cdot 10^5$)— довжину перестановки.

Другий рядок містить $n$ цілих чисел $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$, всі числа попарно різні) — елементи перестановки.

Çıxış verilənləri

Виведіть кількість секунд, яка пройде, поки процес не завершиться, за модулем $10^9+7$.

Nümunələr

Qeyd

В першому прикладі маємо:

$(1,4,2,3)\to (1,4,3,2)\to (1,3,4,2)$: $2$ секунди.

$(1,3,4,2)\to (1,3,2,4)$: $1$ секунда.

$(1,3,2,4)\to (1,2,3,4)\to (1,2,4,3)$: $2$ секунди.

$(1,2,4,3)\to (1,2,3,4)$: $1$ секунда.

Всього $6$ секунд.