Evariste 第三次尝试参加 École Polytechnique 的入学考试。他很快就解决了所有题目，但考官指责他缺乏解释。考官试图让 Evariste 失败，并给了他以下任务：对于给定的长度为 $N$ 的排列 $p$，计算满足对于所有 $1 \le i \le N$ 都有 $p_{q_i} = q_{p_i}$ 的偶排列 $q$ 的数量。由于这个数字可能非常大，考官希望得到它对 $10^9 + 7$ 取模的结果。

如果一个排列包含偶数个逆序对，则称其为偶排列。排列 $p$ 的逆序对是指满足 $i < j$ 且 $p_i > p_j$ 的索引对 $(i, j)$。

不幸的是，对于完全不知道正确答案的考官来说，Galois 在一秒钟内就解决了这个问题。你应该帮助考官告诉他答案，否则年轻的 Evariste 又会被拒绝。

输入格式

第一行包含一个整数 $N$，表示排列的长度 ($1 \le N \le 500\,000$)。

第二行描述排列 $p$ 本身，包含 $N$ 个整数 $p_i$ ($1 \le p_i \le N$，$i \neq j$ 时 $p_i \neq p_j$)。

输出格式

计算满足条件 $p_{q_i} = q_{p_i}$ 的偶排列 $q$ 的数量，并输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
3 1 2

样例输出 1

3

样例输入 2

3
2 1 3

样例输出 2

1

说明

在第一个样例中，有三个合适的排列：$(1, 2, 3), (2, 3, 1), (3, 1, 2)$。它们都是偶排列。

在第二个样例中，有两个合适的排列：$(1, 2, 3), (2, 1, 3)$。然而，只有第一个排列是偶排列。