Tenemos un arreglo ordenado ~[1,2,\dots,n]~ y una permutación ~p_1,p_2,\dots,p_n~. En cada ronda, todos los elementos se mueven según la permutación: el elemento en la posición ~i~ se mueve a la posición ~p_i~.

¿Después de cuántas rondas se ordena el arreglo por primera vez?

Entrada

La primera línea tiene un entero ~n~. La siguiente línea contiene ~n~ enteros ~p_1,p_2,\dots,p_n~.

Salida

Imprime el número de rondas módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~

Ejemplo de Entrada

8
5 3 2 6 4 1 8 7

Ejemplo de Salida

4

Explicación: El arreglo cambia de la siguiente manera después de las rondas:

Ronda 1: [6,3,2,5,1,4,8,7]
Ronda 2: [4,2,3,1,6,5,7,8]
Ronda 3: [5,3,2,6,4,1,8,7]
Ronda 4: [1,2,3,4,5,6,7,8]