给定一个整数数组 $$$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]$$$。可以证明没有其他可实现的数组。