BTtown consiste en $n$ casas, numeradas del 1 al $n$. Las ubicaciones de las casas se describen mediante una permutación $p_1, \dots, p_n$: las casas $i$ y $p_i$ se consideran vecinas. Si $p_i = i$, significa que la casa $i$-ésima no tiene vecinos.

Problemas técnicos en la central eléctrica de la ciudad obligaron al gobierno municipal a desconectar las casas de la red eléctrica una por una. Supongamos que el orden de los cortes se describe mediante la permutación $q_1, \dots, q_n$. Inicialmente, todas las casas están conectadas a la red eléctrica. Durante el día $i$-ésimo, la casa numerada $q_i$ se desconecta de la red.

Para aliviar la situación, los ciudadanos estarán obligados a ayudar a sus vecinos necesitados: los residentes de las casas que aún están conectadas a la red deberán tender cables hacia las casas vecinas que ya han sido desconectadas de la red. Cabe mencionar que esto NO conducirá a la reconexión de la casa vecina a la red.

En cualquier momento, se cumplirá lo siguiente: Un cable conecta dos casas si y solo si son vecinas y solo una de ellas está conectada a la red eléctrica. Por lo tanto, si ambas casas son desconectadas de la red, los cables que podrían haber existido entre las casas anteriormente se eliminan.

Al final de cada día, la ciudad estará dividida en grupos de casas conectadas por cables tendidos por los ciudadanos. Para analizar la estabilidad de la red eléctrica, es importante realizar un seguimiento del número de dichos grupos. La inestabilidad del orden de corte $q$ es la suma del número de tales grupos a lo largo de cada uno de los $n$ días.

El gobierno de la ciudad aún no ha decidido el orden $q$ y es necesario encontrar la suma de las inestabilidades sobre todos los órdenes posibles. Ayude a la ciudad a calcular el valor módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^6$). La segunda línea contiene $n$ enteros separados por espacios $p_1, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ si $i \neq j$).

Salida

Imprima un entero: el resto de la división de la suma de las inestabilidades sobre todos los posibles órdenes de corte entre $10^9 + 7$.

Subtareas

Este problema contiene 7 subtareas, que cumplen los siguientes requisitos:

1. $n \le 8$. Valor: 8 puntos.
2. $n \le 18$. Valor: 10 puntos.
3. $n \le 30$. Valor: 13 puntos.
4. $n \le 2000$. Valor: 22 puntos.
5. $n \le 100000$, $p_i = n - i + 1$. Valor: 16 puntos.
6. $n \le 100000$. Valor: 12 puntos.
7. Restricciones originales del problema. Valor: 19 puntos.

Ejemplos

Entrada 1

2
2 1

Salida 1

6

Entrada 2

4
3 4 2 1

Salida 2

232

Nota

Consideremos el segundo ejemplo con el orden $q = [4, 3, 2, 1]$. Inicialmente, todas las casas están conectadas a la red.

1. Durante el primer día, la 4-ta casa se corta de la red. Los residentes de las casas 1 y 2 notarán que su vecino no tiene electricidad y tenderán los cables. Por lo tanto, las casas 1, 2 y 4 formarán un grupo conectado por cables ciudadanos. Al mismo tiempo, la 3-ra casa se considerará un grupo separado. El número de grupos es 2.
2. Durante el segundo día, la 3-ra casa se corta de la red. Los residentes de las casas 1 y 2 volverán a tender los cables. Las 4 casas estarán conectadas por cables. El número de grupos es 1.
3. En el tercer día, la 2-da casa se desconecta. Como resultado, ambos cables previamente unidos a la 2-da casa se eliminan. Ahora hay dos grupos: $[1, 3, 4]$ y $[2]$. El número de grupos es 2.
4. Finalmente, la primera casa se desconecta. Ambos cables previamente unidos a la primera casa se eliminan y cada casa formará un grupo separado. El número de grupos es 4.

Como resultado, la inestabilidad del orden $q = [4, 3, 2, 1]$ es $2+1+2+4=9$.