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

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

2 секунди
256 мегабайтів
Дуже складна

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

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

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

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

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

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