配点 : 1400 点
問題文
長さ N の数列 a が与えられます。
1 から N までの整数の順列 p であって、次の条件を満たすものは何通りでしょうか?
109+7 で割った余りを求めてください。
- 各 1≤i≤N について、pi=ai または ppi=ai の少なくとも一方が成り立つ。
制約
- 1≤N≤105
- ai は整数である。
- 1≤ai≤N
入力
入力は以下の形式で標準入力から与えられる。
N
a1 a2 ... aN
出力
条件を満たす順列 p の個数を 109+7 で割った余りを出力せよ。
3
1 2 3
4
次の 4 通りです。
- (1,2,3)
- (1,3,2)
- (3,2,1)
- (2,1,3)
たとえば (1,3,2) は、p1=1, pp2=2, pp3=3 となっています。
2
1 1
1
次の 1 通りです。
3
2 1 1
2
次の 2 通りです。
- (2,3,1)
- (3,1,2)
3
1 1 1
0
13
2 1 4 3 6 7 5 9 10 8 8 9 11
6