该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

幻象｢Luna Clock｣(月神之钟)

题目描述

给定一个长度为 $n$ 的数组 $a_{1},a_{2},\dots,a_{n}$，满足 $1 \le a_{i} \le n$。

你可以进行任意次操作。每次选择一个下标 $i$，先令 $j$ 等于操作开始时的 $a_{i}$，再交换 $a_{i}$ 与 $a_{j}$ 的值。也就是说，第二个位置由交换前的数组确定。求经过操作能够得到多少个不同的数组。

答案对 $10^{9}+7$ 取模。

输入格式

第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_{1},a_{2},\dots,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

样例3解释

函数图中 $1 \to 2 \to 3 \to 1$ 构成一个三元环，点 $4,5$ 指向点 $1$，点 $6$ 指向点 $2$。各点原始入度为 $d_{1}=3$，$d_{2}=2$，$d_{3}=1$，$d_{4}=d_{5}=d_{6}=0$。

环外点的贡献均为 $1$。三元环的贡献为 $\red{ \left(d_{1}+1\right)\left(d_{2}+1\right)}$$\red{\left(d_{3}+1\right)}$-$\red{\left(d_{1}+d_{2}+d_{3}\right)}$=$\red{4 \times 3 \times 2-6=18, }$ 因此答案为 $18$。

数据范围

对于前10%的数据， $n \le 10$。 另有20%的数据，所有 $a_{i}$ 互不相同。 另有20%的数据， $a_{i} \le \max(i-1,1)$。 另有20%的数据， $a_{i} \le i$。 对于100%的数据， $1 \le n \le 10^{6}$， $1 \le a_{i} \le n$。