编码员 ZS 和狒狒克里斯已经探索 Udayland 相当一段时间了。他们意识到它由编号为 1 到 n 的 n 个城镇组成。
乌代兰有 n 条有向道路。其中第 i 个从城镇 i 前往其他城镇 ai (ai ≠ i)。 ZS编码器可以翻转Udayland中任何道路的方向,即如果翻转之前是从A镇到B镇,那么翻转后就会从B镇到A镇。
ZS 编码员认为 Udayland 中的道路令人困惑,如果存在一系列不同的城镇 A1、A2、...、Ak (k > 1),使得对于每个 1 ≤ i < k,有一条从城镇 Ai 到城镇 Ai + 1 的道路,以及另一条从城镇 Ak 到城镇 A1 的道路。换句话说,如果其中一些道路形成了某些城镇的有向循环,那么这些道路就会变得混乱。
现在编码员 ZS 想知道初始配置中有多少组道路(有 2n 种变体)他可以选择翻转,这样在将组中的每条道路翻转一次后,生成的网络就不会混乱。
请注意,翻转后允许存在多于一条从某个城镇出发的有向道路,也可能有一些没有道路从该城镇引出的城镇,或任意一对城市之间的多条道路。
输入
输入的第一行包含单个整数 n (2 ≤ n ≤ 2·105) - 乌代兰的城镇数量。
下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n, ai ≠ i),ai 表示从城镇 i 到城镇 ai 的道路。
输出
打印一个整数 - 翻转某些道路集的方法数量,以便生成的所有道路集不会混淆。由于这个数字可能太大,请打印对 109 + 7 取模的答案。
示例
输入 #1
3 2 3 1
输出 #1
6
输入 #2
4 2 1 1 1
输出 #2
8
输入 #3
5 2 4 2 5 3
输出 #3
28
注意
考虑第一个示例案例。有3个镇、3条道路。城镇编号为 1 到 3,道路最初为 $$1 \rightarrow 2$$、$$2\rightarrow3$$、$$\overset{3}{\rightarrow}1$$。按此顺序对道路 1 至 3 进行编号。
编码器 ZS 可以翻转的道路组(以使它们不会混淆)为 {1}、{2}、{3}、{1, 2}、{1, 3}、{2, 3}。请注意,空集是无效的,因为如果没有道路翻转,则城镇 1、2、3 形成有向循环,因此会造成混乱。同样,翻转所有道路也令人困惑。因此,编码器可以翻转总共 6 个可能的 ZS 组。
示例图像显示了从第一个示例开始确定道路方向的所有可能方法,以使网络不会混淆。