[AGC008E] Next or Nextnext

给定正整数 $n$ 和一个长度为 $n$ 的序列 $a$，问有多少长度为 $n$ 的排列 $p$，满足对于任意 $i$ 有 $p_i=a_i$ 或 $p_{p_i}=a_i$。 答案对 $10^9+7$ 取模。 $n \leq 10^5$。

[problemUrl]: https://atcoder.jp/contests/agc008/tasks/agc008_e 長さ $ 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 $ で割った余りを出力せよ。

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) $