CF1863G.Swaps

You are given an array of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$). You can perform the following operation several (possibly, zero) times:

• pick an arbitrary $i$ and perform swap$(a_i, a_{a_i})$.

How many distinct arrays is it possible to attain? Output the answer modulo $(10^9 + 7)$.

给你一个整数数组 $a_1, a_2, \dots, a_n$（其中 $1 \le a_i \le n$）。你可以执行以下操作若干次（可以为零次）：

• 任选一个下标 $i$，并执行交换操作 $\text{swap}(a_i, a_{a_i})$。

问：一共能到达多少种不同的数组？答案对 $(10^9 + 7)$ 取模。

The first line contains an integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le n$).

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1\le a_i\le n$）。

Output the number of attainable arrays modulo $(10^9 + 7)$.

输出可达成数组的数量对 $(10^9 + 7)$ 取模的结果。

In the first example, the initial array is $[1, 1, 2]$. If we perform the operation with $i = 3$, we swap $a_3$ and $a_2$, obtaining $[1, 2, 1]$. One can show that there are no other attainable arrays.

In the second example, the four attainable arrays are $[2, 1, 4, 3]$, $[1, 2, 4, 3]$, $[1, 2, 3, 4]$, $[2, 1, 3, 4]$. One can show that there are no other attainable arrays.

在第一个例子中，初始数组为 $[1, 1, 2]$。若对 $i = 3$ 执行操作，则交换 $a_3$ 与 $a_2$，得到 $[1, 2, 1]$。可以证明不存在其他可达的数组。

在第二个例子中，四个可达的数组分别为 $[2, 1, 4, 3]$、$[1, 2, 4, 3]$、$[1, 2, 3, 4]$ 和 $[2, 1, 3, 4]$。可以证明不存在其他可达的数组。