AtCoder Grand Contest 008
翻译中…
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$.
翻译中…
样例
Input #1
3
1 2 3
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$.
Input #2
2
1 1
Output #2
1
The following one permutation satisfies the condition:
- $(2, 1)$
Input #3
3
2 1 1
Output #3
2
The following two permutations satisfy the condition:
- $(2, 3, 1)$
- $(3, 1, 2)$
Input #4
3
1 1 1
Output #4
0
Input #5
13
2 1 4 3 6 7 5 9 10 8 8 9 11
Output #5
6
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。