BTtown se compose de $n$ maisons, numérotées de $1$ à $n$. L'emplacement des maisons est décrit par une permutation $p_1, \dots, p_n$ : les maisons $i$ et $p_i$ sont considérées comme voisines. Si $p_i = i$, cela signifie que la $i$-ème maison n'a pas de voisins.

Des problèmes techniques à la centrale électrique de la ville ont contraint le gouvernement municipal à couper les maisons du réseau électrique une par une. Supposons que l'ordre des coupures soit décrit par la permutation $q_1, \dots, q_n$. Initialement, chaque maison est connectée au réseau électrique. Durant le $i$-ème jour, la maison numérotée $q_i$ est déconnectée du réseau.

Pour faciliter la situation, les citoyens seront obligés d'aider leurs voisins dans le besoin : les résidents des maisons encore connectées au réseau devront tirer des câbles vers les maisons voisines qui ont été coupées du réseau. Il convient de mentionner que cela ne conduira PAS à la reconnexion de la maison voisine au réseau.

À tout moment, les conditions suivantes seront respectées :

• Un câble relie deux maisons si et seulement si elles sont voisines et qu'une seule d'entre elles est connectée au réseau électrique.
• Par conséquent, si les deux maisons sont coupées du réseau, les câbles qui auraient pu relier les maisons auparavant sont retirés.

À la fin de chaque journée, la ville sera divisée en groupes de maisons connectées par des câbles installés par les citoyens. Pour analyser la stabilité du réseau électrique, il est important de suivre le nombre de ces groupes. L'instabilité de l'ordre de coupure $q$ est la somme du nombre de ces groupes sur chacun des $n$ jours.

Le gouvernement municipal n'a pas encore décidé de l'ordre $q$ et il est nécessaire de trouver la somme des instabilités sur tous les ordres possibles. Aidez la ville à calculer cette valeur modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$). La deuxième ligne contient $n$ entiers séparés par des espaces $p_1, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ si $i \neq j$).

Sortie

Affichez un entier — le reste de la division de la somme des instabilités sur tous les ordres de coupure possibles par $10^9 + 7$.

Sous-tâches

Ce problème contient 7 sous-tâches, qui répondent aux exigences suivantes :

1. $n \le 8$. Vaut 8 points.
2. $n \le 18$. Vaut 10 points.
3. $n \le 30$. Vaut 13 points.
4. $n \le 2000$. Vaut 22 points.
5. $n \le 100000$, $p_i = n - i + 1$. Vaut 16 points.
6. $n \le 100000$. Vaut 12 points.
7. Contraintes du problème original. Vaut 19 points.

Exemples

Entrée 1

2
2 1

Sortie 1

6

Entrée 2

4
3 4 2 1

Sortie 2

232

Remarque

Considérons le deuxième exemple avec l'ordre $q = [4, 3, 2, 1]$. Initialement, toutes les maisons sont connectées au réseau.

1. Durant le premier jour, la 4-ème maison est coupée du réseau. Les résidents des maisons 1 et 2 remarqueront que leur voisin n'a plus d'électricité et tireront les câbles. Ainsi, les maisons 1, 2, 4 formeront un groupe connecté par des câbles citoyens. En même temps, la 3-ème maison sera considérée comme un groupe séparé. Le nombre de groupes est 2.
2. Durant le deuxième jour, la 3-ème maison sera coupée du réseau. Les résidents des maisons 1 et 2 tireront à nouveau les câbles. Les 4 maisons seront connectées par des câbles. Le nombre de groupes est 1.
3. Le troisième jour, la 2-ème maison est déconnectée. En conséquence, les deux câbles précédemment attachés à la 2-ème maison sont retirés. Il y a maintenant deux groupes — $[1, 3, 4]$ et $[2]$. Le nombre de groupes est 2.
4. Enfin, la première maison est déconnectée. Les deux câbles précédemment attachés à la première maison sont retirés et chaque maison formera un groupe séparé. Le nombre de groupes est 4.

En résultat, l'instabilité de l'ordre $q = [4, 3, 2, 1]$ est $2+1+2+4=9$.