题目描述

長さ $N$ の数列 $a$ が与えられます。 $1$ から $N$ までの整数の順列 $p$ であって、次の条件を満たすものは何通りでしょうか？ $10^9\ +\ 7$ で割った余りを求めてください。

• 各 $1\ <\ =\ i\ <\ =\ N$ について、$p_i\ =\ a_i$ または $p_{p_i}\ =\ a_i$ の少なくとも一方が成り立つ。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たす順列 $p$ の個数を $10^9\ +\ 7$ で割った余りを出力せよ。

题目大意

给定正整数 $n$ 和一个长度为 $n$ 的序列 $a$，问有多少长度为 $n$ 的排列 $p$，满足对于任意 $i$ 有 $p_i=a_i$ 或 $p_{p_i}=a_i$。

答案对 $10^9+7$ 取模。

$n \leq 10^5$。

3
1 2 3

4

2
1 1

1

3
2 1 1

2

3
1 1 1

0

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

6

提示

制約

• $1\ <\ =\ N\ <\ =\ 10^5$
• $a_i$ は整数である。
• $1\ <\ =\ a_i\ <\ =\ N$

Sample Explanation 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$ となっています。

Sample Explanation 2

次の $1$ 通りです。 - $(2,\ 1)$

Sample Explanation 3

次の $2$ 通りです。 - $(2,\ 3,\ 1)$ - $(3,\ 1,\ 2)$