BTtown은 $1$부터 $n$까지 번호가 매겨진 $n$개의 집으로 구성되어 있습니다. 집의 위치는 순열 $p_1, \dots, p_n$으로 설명되며, 집 $i$와 $p_i$는 서로 이웃입니다. 만약 $p_i = i$라면, $i$번째 집은 이웃이 없음을 의미합니다.

도시 중앙 발전소의 기술적 문제로 인해 시 정부는 집들을 하나씩 전력망에서 차단해야 합니다. 차단 순서가 순열 $q_1, \dots, q_n$으로 주어진다고 가정합시다. 처음에 모든 집은 전력망에 연결되어 있습니다. $i$번째 날에는 번호가 $q_i$인 집이 전력망에서 차단됩니다.

상황을 완화하기 위해, 시민들은 도움이 필요한 이웃을 도와야 합니다. 즉, 여전히 전력망에 연결된 집의 거주자들은 전력망에서 차단된 이웃 집으로 케이블을 연결해야 합니다. 이 과정은 차단된 이웃 집을 다시 전력망에 연결하는 것은 아님을 유의하십시오.

어느 시점에서든 다음 규칙이 성립합니다: 케이블은 두 집이 서로 이웃이고 그중 하나만 전력망에 연결되어 있을 때만 두 집 사이에 연결됩니다. 따라서, 두 집 모두 전력망에서 차단되면, 그전에 두 집 사이에 연결되었을 수 있는 케이블은 제거됩니다.

매일이 끝날 때, 도시는 시민들이 설치한 케이블로 연결된 집들의 그룹으로 나뉩니다. 전력망의 안정성을 분석하기 위해 이러한 그룹의 수를 추적하는 것이 중요합니다. 차단 순서 $q$의 불안정성(instability)은 $n$일 동안의 각 날에 대한 이러한 그룹 수의 합입니다.

시 정부는 아직 차단 순서 $q$를 결정하지 않았으며, 모든 가능한 차단 순서에 대한 불안정성의 합을 구해야 합니다. 이 값을 $10^9 + 7$로 나눈 나머지를 계산하여 도시를 도우십시오.

입력

첫 번째 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 두 번째 줄에는 $n$개의 공백으로 구분된 정수 $p_1, \dots, p_n$ ($1 \le p_i \le n$, $i \neq j$이면 $p_i \neq p_j$)이 주어집니다.

출력

모든 가능한 차단 순서에 대한 불안정성의 합을 $10^9 + 7$로 나눈 나머지를 출력하십시오.

서브태스크

이 문제는 다음 요구 사항을 충족하는 7개의 서브태스크로 구성됩니다:

1. $n \le 8$. 8점.
2. $n \le 18$. 10점.
3. $n \le 30$. 13점.
4. $n \le 2000$. 22점.
5. $n \le 100000, p_i = n - i + 1$. 16점.
6. $n \le 100000$. 12점.
7. 원래 문제의 제한 조건. 19점.

예제

예제 1

2
2 1

출력 1

6

예제 2

4
3 4 2 1

출력 2

232

참고

두 번째 예제에서 차단 순서 $q = [4, 3, 2, 1]$인 경우를 고려해 봅시다. 처음에 모든 집은 전력망에 연결되어 있습니다.

1. 첫째 날, 4번 집이 전력망에서 차단됩니다. 1번과 2번 집의 거주자들은 이웃이 전기를 공급받지 못하는 것을 확인하고 케이블을 연결합니다. 따라서 1, 2, 4번 집은 시민들이 설치한 케이블로 연결된 하나의 그룹을 형성합니다. 동시에 3번 집은 별도의 그룹으로 간주됩니다. 그룹의 수는 2개입니다.
2. 둘째 날, 3번 집이 전력망에서 차단됩니다. 1번과 2번 집의 거주자들은 다시 케이블을 연결합니다. 4개의 집 모두가 케이블로 연결됩니다. 그룹의 수는 1개입니다.
3. 셋째 날, 2번 집이 차단됩니다. 결과적으로 2번 집에 연결되었던 두 케이블이 모두 제거됩니다. 이제 [1, 3, 4]와 [2]라는 두 개의 그룹이 생깁니다. 그룹의 수는 2개입니다.
4. 마지막으로, 1번 집이 차단됩니다. 1번 집에 연결되었던 두 케이블이 모두 제거되고 모든 집이 각각 별도의 그룹을 형성합니다. 그룹의 수는 4개입니다.

결과적으로 차단 순서 $q = [4, 3, 2, 1]$의 불안정성은 $2+1+2+4=9$입니다.