AT_agc008_e.[AGC008E] Next or Nextnext

给定一个长度为 $N$ 的数列 $a$。请问有多少个 $1$ 到 $N$ 的整数的排列 $p$ 满足以下条件？请输出答案对 $10^9+7$ 取模的结果。

• 对于每个 $1 \leq i \leq N$，至少有 $p_i = a_i$ 或 $p_{p_i} = a_i$ 成立。

输入通过标准输入给出，格式如下：

$N$ $a_1$ $a_2$ $...$ $a_N$

输出满足条件的排列 $p$ 的个数，对 $10^9+7$ 取模。

限制条件

• $1 \leq N \leq 10^5$
• $a_i$ 是整数。
• $1 \leq a_i \leq N$

样例解释 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

只有以下 $1$ 种排列：

• $(2, 1)$

样例解释 3

共有以下 $2$ 种排列：

• $(2, 3, 1)$
• $(3, 1, 2)$

由 ChatGPT 4.1 翻译