310638: CF1863G. Swaps

G. Swapstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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)$.

Input

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$).

Output

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

ExamplesInput

3
1 1 2

Output

2

Input

4
2 1 4 3

Output

4

Input

6
2 3 1 1 1 2

Output

18

Note

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.

题目大意：
给定一个由整数组成的数组 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），你可以进行以下操作若干次（可能为零次）：

- 选择任意的 $i$ 并执行 `swap` $ (a_i, a_{a_i}) $。

问可以获取多少个不同的数组。输出答案对 $10^9 + 7$ 取模的结果。

输入输出数据格式：
输入：
- 第一行包含一个整数 $n$（$1 \le n \le 10^6$）。
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

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

示例：
输入：
```
3
1 1 2
```
输出：
```
2
```

输入：
```
4
2 1 4 3
```
输出：
```
4
```

输入：
```
6
2 3 1 1 1 2
```
输出：
```
18
```

注意：
- 在第一个示例中，初始数组是 $[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]$。可以证明没有其他可达数组。题目大意： 给定一个由整数组成的数组 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），你可以进行以下操作若干次（可能为零次）： - 选择任意的 $i$ 并执行 `swap` $ (a_i, a_{a_i}) $。 问可以获取多少个不同的数组。输出答案对 $10^9 + 7$ 取模的结果。 输入输出数据格式： 输入： - 第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。 输出： - 输出可达数组数量对 $10^9 + 7$ 取模的结果。 示例： 输入： ``` 3 1 1 2 ``` 输出： ``` 2 ``` 输入： ``` 4 2 1 4 3 ``` 输出： ``` 4 ``` 输入： ``` 6 2 3 1 1 1 2 ``` 输出： ``` 18 ``` 注意： - 在第一个示例中，初始数组是 $[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]$。可以证明没有其他可达数组。