← 返回题目列表

Codeforces · 1863/G

G. 掉期

中文机器翻译题面 查看原题

给定一个整数数组 $$$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)$$$ 取模。

示例

输入 #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, 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]$$$。可以证明没有其他可实现的数组。