갈루아

에바리스트가 에콜 폴리테크니크 입학시험에 세 번째로 도전한다. 그는 모든 문제를 아주 빠르게 풀었지만, 시험관은 그가 설명을 충분히 하지 않았다며 트집을 잡는다. 시험관은 에바리스트를 떨어뜨리려고 다음과 같은 문제를 낸다. 크기 $N$인 순열 $p$가 주어질 때, 모든 $i$에 대해 $p_{q_i} = q_{p_i}$ ($1 \le i \le N$)를 만족하는 크기 $N$인 짝순열 $q$의 개수를 세어라. 이 수는 매우 클 수 있으므로 시험관은 $10^9 + 7$로 나눈 나머지를 알고 싶어 한다.

순열이 짝이라는 것은 역전의 개수가 짝수라는 뜻이다. 순열 $p$의 역전은 $i < j$이고 $p_i > p_j$인 첨자 쌍 $(i, j)$이다.

정답을 전혀 모르는 시험관에게 안타깝게도, 갈루아는 단 1초 만에 이 문제를 풀어냈다. 당신이 시험관을 도와 답을 알려주어야 한다. 그렇지 않으면 어린 에바리스트는 또다시 거절당할 것이다.

입력의 첫째 줄에는 순열의 길이를 나타내는 정수 $N$이 주어진다 ($1 \le N \le 500\,000$).

둘째 줄에는 순열 $p$가 주어지며, $N$개의 정수 $p_i$가 포함된다 ($1 \leq p_i \leq N$, $i \ne j$인 모든 $i, j$에 대해 $p_i \ne p_j$).

조건 $p_{q_i} = q_{p_i}$를 만족하는 짝순열 $q$의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 예에서 조건을 만족하는 순열은 (1, 2, 3), (2, 3, 1), (3, 1, 2) 세 개이다. 모두 짝순열이다.

두 번째 예에서 조건을 만족하는 순열은 (1, 2, 3), (2, 1, 3) 두 개이다. 그러나 이 중 짝순열은 첫 번째뿐이다.