/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1400 点
問題文
長さ N の数列 a が与えられます。 1 から N までの整数の順列 p であって、次の条件を満たすものは何通りでしょうか？ 10^9 + 7 で割った余りを求めてください。
- 各 1 ≤ i ≤ N について、p_i = a_i または p_{p_i} = a_i の少なくとも一方が成り立つ。
制約
- 1 ≤ N ≤ 10^5
- a_i は整数である。
- 1 ≤ a_i ≤ N
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
条件を満たす順列 p の個数を 10^9 + 7 で割った余りを出力せよ。
入力例 1
3 1 2 3
出力例 1
4
次の 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
次の 1 通りです。
- (2, 1)
入力例 3
3 2 1 1
出力例 3
2
次の 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
Score : 1400 points
Problem Statement
You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?
- For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.
Find the count modulo 10^9 + 7.
Constraints
- 1 ≤ N ≤ 10^5
- a_i is an integer.
- 1 ≤ a_i ≤ N
Input
The input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.
Sample Input 1
3 1 2 3
Sample Output 1
4
The following four permutations satisfy the condition:
- (1, 2, 3)
- (1, 3, 2)
- (3, 2, 1)
- (2, 1, 3)
For example, (1, 3, 2) satisfies the condition because p_1 = 1, p_{p_2} = 2 and p_{p_3} = 3.
Sample Input 2
2 1 1
Sample Output 2
1
The following one permutation satisfies the condition:
- (2, 1)
Sample Input 3
3 2 1 1
Sample Output 3
2
The following two permutations satisfy the condition:
- (2, 3, 1)
- (3, 1, 2)
Sample Input 4
3 1 1 1
Sample Output 4
0
Sample Input 5
13 2 1 4 3 6 7 5 9 10 8 8 9 11
Sample Output 5
6