分数: 1400 点
问题陈述
给你一个整数序列 a 长度 N。 有多少种排列 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
输出
打印排列数 p 满足条件,取模 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