BTtown składa się z $n$ domów, ponumerowanych od $1$ do $n$. Położenie domów opisuje permutacja $p_1, \dots, p_n$: domy $i$ oraz $p_i$ są uważane za sąsiadujące. Jeśli $p_i = i$, oznacza to, że $i$-ty dom nie ma sąsiadów.

Problemy techniczne w centralnej elektrowni miasta zmusiły władze do odłączania domów od sieci elektrycznej jeden po drugim. Niech kolejność odłączeń będzie opisana permutacją $q_1, \dots, q_n$. Początkowo każdy dom jest podłączony do sieci. W $i$-tym dniu dom o numerze $q_i$ zostaje odłączony od sieci.

Aby złagodzić sytuację, mieszkańcy będą zobowiązani pomóc swoim potrzebującym sąsiadom: mieszkańcy domów wciąż podłączonych do sieci będą musieli poprowadzić kable do sąsiadujących domów, które zostały odłączone od sieci. Należy zaznaczyć, że NIE doprowadzi to do ponownego podłączenia sąsiadującego domu do sieci.

W każdej chwili czasu zachodzą następujące warunki: Kabel biegnie między dwoma domami wtedy i tylko wtedy, gdy są one sąsiadami i tylko jeden z nich jest podłączony do sieci elektrycznej. W związku z tym, jeśli oba domy zostaną odłączone od sieci, kable, które mogły biec między nimi wcześniej, zostają usunięte.

Pod koniec każdego dnia miasto będzie podzielone na grupy domów połączonych kablami poprowadzonymi przez mieszkańców. Aby przeanalizować stabilność sieci energetycznej, ważne jest śledzenie liczby takich grup. Niestabilność kolejności odłączeń $q$ to suma liczb takich grup w każdym z $n$ dni.

Władze miasta nie zdecydowały jeszcze o kolejności $q$ i konieczne jest znalezienie sumy niestabilności dla wszystkich możliwych kolejności. Pomóż miastu obliczyć tę wartość modulo $10^9 + 7$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^6$). Druga linia zawiera $n$ liczb całkowitych oddzielonych spacjami $p_1, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ dla $i \neq j$).

Wyjście

Wypisz jedną liczbę całkowitą – resztę z dzielenia sumy niestabilności dla wszystkich możliwych kolejności odłączeń przez $10^9 + 7$.

Podzadania

Problem zawiera 7 podzadań, które spełniają następujące wymagania: 1. $n \le 8$. Warte 8 punktów. 2. $n \le 18$. Warte 10 punktów. 3. $n \le 30$. Warte 13 punktów. 4. $n \le 2000$. Warte 22 punkty. 5. $n \le 100000$, $p_i = n - i + 1$. Warte 16 punktów. 6. $n \le 100000$. Warte 12 punktów. 7. Oryginalne ograniczenia problemu. Warte 19 punktów.

Przykład

Wejście 1

2
2 1

Wyjście 1

6

Wejście 2

4
3 4 2 1

Wyjście 2

232

Uwagi

Rozważmy drugi przykład z kolejnością $q = [4, 3, 2, 1]$. Początkowo wszystkie domy są podłączone do sieci.

1. Pierwszego dnia 4-ty dom zostaje odłączony od sieci. Mieszkańcy domów 1 i 2 zauważą, że ich sąsiad nie ma prądu i poprowadzą kable. W ten sposób domy 1, 2, 4 utworzą grupę połączoną kablami mieszkańców. Jednocześnie 3-ci dom będzie uważany za oddzielną grupę. Liczba grup wynosi 2.
2. Drugiego dnia 3-ci dom zostaje odłączony od sieci. Mieszkańcy domów 1 i 2 ponownie poprowadzą kable. Wszystkie 4 domy będą połączone kablami. Liczba grup wynosi 1.
3. Trzeciego dnia 2-gi dom zostaje odłączony. W rezultacie oba kable wcześniej przymocowane do 2-go domu zostają usunięte. Teraz istnieją dwie grupy — $[1, 3, 4]$ oraz $[2]$. Liczba grup wynosi 2.
4. Na koniec pierwszy dom zostaje odłączony. Oba kable wcześniej przymocowane do pierwszego domu zostają usunięte i każdy dom tworzy oddzielną grupę. Liczba grup wynosi 4.

W rezultacie niestabilność kolejności $q = [4, 3, 2, 1]$ wynosi $2+1+2+4=9$.