问题描述

给定一个长度为 $N$ 的整数序列 $a$。有多少个满足以下条件的排列 $p$，其中 $p$ 是整数 $1$ 到 $N$ 的所有数字的一个排列？

• 对于每个 $1 ≤ i ≤ N$，至少有以下两种情况之一成立：$p_i = a_i$ 且 $p_{p_i} = a_i$。

求满足条件的排列数对 $10^9 + 7$ 取模的结果。

约束条件

• $1 ≤ N ≤ 10^5$
• $a_i$ 是整数。
• $1 ≤ a_i ≤ N$

---

输入

输入以以下格式从标准输入给出：

$N$ $a_1$ $a_2$ $...$ $a_N$

输出

打印满足条件的排列数对 $10^9 + 7$ 取模的结果。

---

示例 1

3
1 2 3

输出 1

4

满足条件的四个排列为：

• $(1, 2, 3)$
• $(1, 3, 2)$
• $(3, 2, 1)$
• $(2, 1, 3)$

例如，$(1, 3, 2)$ 满足条件，因为 $p_1 = 1$，$p_{p_2} = 2$ 和 $p_{p_3} = 3$。

---

示例 2

2
1 1

输出 2

1

满足条件的一个排列为：

• $(2, 1)$

---

示例 3

3
2 1 1

输出 3

2

满足条件的两个排列为：

• $(2, 3, 1)$
• $(3, 1, 2)$

---

示例 4

3
1 1 1

输出 4

0

---

示例 5

13
2 1 4 3 6 7 5 9 10 8 8 9 11

输出 5

6