交换计数

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$，满足 $1\le a_i\le n$。

你可以进行任意多次（也可以一次都不进行）以下操作：

• 选择一个下标 $i$，交换 $a_i$ 与 $a_{a_i}$。

求从初始数组出发能够得到的不同数组总数。答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示可达数组总数对 $10^9+7$ 取模的结果。

样例输入 1

3
1 1 2

样例输出 1

2

样例输入 2

4
2 1 4 3

样例输出 2

4

样例输入 3

6
2 3 1 1 1 2

样例输出 3

18

样例说明

在样例 1 中，初始数组为 $[1,1,2]$。选择 $i=3$ 后，交换 $a_3$ 与 $a_2$，得到 $[1,2,1]$。可以证明只有这两个数组可达。

数据范围

对所有数据，$1\le n\le 10^6$，$1\le a_i\le n$。

每个测试点独立计分。