Cuando no hay nada que hacer y solo hay una permutación en casa#12857

Cuando no hay nada que hacer y solo hay una permutación en casa

2 segundos
256 megabytes
Muy difícil

Se te da una permutación (p_1, p_2, \ldots, p_n) de los números del al .

Puedes realizar la siguiente operación con ella:

En una iteración haces lo siguiente:

Aplicas esta iteración a la permutación resultante hasta que se convierta en la permutación identidad (es decir, igual a (1, 2, 3, \ldots, n)). ¿Cuánto tiempo tomará esto? Como este número puede ser muy grande, imprímelo módulo 10^9+7.

Una permutación se considera lexicográficamente menor que una permutación si existe un índice tal que p_j = q_j para todo j<i, y además p_i<q_i.

Entrada

La primera línea contiene un entero (1 \le n \le 2\cdot 10^5) — la longitud de la permutación.

La segunda línea contiene enteros p_1, p_2, \ldots, p_n (1 \le p_i \le n, todos los números son distintos dos a dos) — los elementos de la permutación.

Salida

Imprime la cantidad de segundos que pasarán hasta que el proceso termine, módulo 10^9+7.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

En el primer ejemplo tenemos:

(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): segundos.

(1, 3, 4, 2) \to (1, 3, 2, 4): segundo.

(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): segundos.

(1, 2, 4, 3) \to (1, 2, 3, 4): segundo.

En total, segundos.