19150번 - Galois 다국어

Third time Evariste is attempting the entrance examination for the École Polytechnique. He managed to solve all the tasks very quickly, but the examiner accuses him of lack of explanations. He tries to make Evariste fail and gives him the following task: for the given permutation $p$ of size $N$, count the number of even permutations $q$ of size $N$ such that $p_{q_i} = q_{p_i}$ for all $i$ from $1$ to $N$. As this number can be very large, the examiner wants to know it modulo $10^9 + 7$.

A permutation is said to be even if it contains an even number of inversions. An inversion of a permutation $p$ is a pair of indices $(i, j)$ such that $i < j$ and $p_i > p_j$

Unfortunately for the examiner, who has no idea about the correct answer, Galois managed to solve the problem in only one second. You should help examiner and tell him the answer, or young Evariste will be denied again.

The first line of the input contains a single integer $N$, which denotes the length of the permutation ($1 \le N \le 500\,000$).

The second line describes the permutation $p$ itself and contains $N$ integers $p_i$ ($1 \leq p_i \leq N$, $p_i \ne p_j$ for all $i \ne j$).

Count the number of even permutations $q$ that satisfy the condition $p_{q_i} = q_{p_i}$, and output it modulo $10^9 + 7$.

In the first example there are three appropriate permutations: (1, 2, 3), (2, 3, 1), (3, 1, 2). All of them are even.

In the second example there are two appropriate permutations: (1, 2, 3), (2, 1, 3). However, only first of these permutations is even.