4589: Directed Roads
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：6
通过：2
题目描述
D. Directed Roads
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
ZS the Coder and Chris the Baboon has explored Udayland for quite some time. They realize that it consists of n towns numbered from 1 to n.
There are n directed roads in the Udayland. i-th of them goes from town i to some other town ai (ai≠i). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town A to town B before the flip, it will go from town B to town A after.
ZS the Coder considers the roads in the Udayland confusing, if there is a sequence of distinct towns A1,A2,...,Ak (k>1) such that for every 1≤i<k there is a road from town Ai to town Ai+1 and another road from town Ak to town A1. In other words, the roads are confusing if some of them form a directed cycle of some towns.
Now ZS the Coder wonders how many sets of roads (there are 2n variants) in initial configuration can he choose to flip such that after flipping each road in the set exactly once, the resulting network will not be confusing.
Note that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.
There are n directed roads in the Udayland. i-th of them goes from town i to some other town ai (ai≠i). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town A to town B before the flip, it will go from town B to town A after.
ZS the Coder considers the roads in the Udayland confusing, if there is a sequence of distinct towns A1,A2,...,Ak (k>1) such that for every 1≤i<k there is a road from town Ai to town Ai+1 and another road from town Ak to town A1. In other words, the roads are confusing if some of them form a directed cycle of some towns.
Now ZS the Coder wonders how many sets of roads (there are 2n variants) in initial configuration can he choose to flip such that after flipping each road in the set exactly once, the resulting network will not be confusing.
Note that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.
Input
The first line of the input contains single integer n (2≤n≤2·105)− the number of towns in Udayland.The next line contains n integers a1,a2,...,an (1≤ai≤n,ai≠i), ai denotes a road going from town i to town ai.
Output
Print a single integer− the number of ways to flip some set of the roads so that the resulting whole set of all roads is not confusing. Since this number may be too large, print the answer modulo 109+7.
Examples
Input
3 2 3 1
Output
6
Input
4 2 1 1 1
Output
8
Input
5 2 4 2 5 3
Output
28
Note
Consider the first sample case. There are 3 towns and 3 roads. The towns are numbered from 1 to 3 and the roads are 
, 
, 
initially. Number the roads 1 to 3 in this order. The sets of roads that ZS the Coder can flip (to make them not confusing) are {1},{2},{3},{1,2},{1,3},{2,3}. Note that the empty set is invalid because if no roads are flipped, then towns 1,2,3 is form a directed cycle, so it is confusing. Similarly, flipping all roads is confusing too. Thus, there are a total of 6 possible sets ZS the Coder can flip.
The sample image shows all possible ways of orienting the roads from the first sample such that the network is not confusing.
编码员ZS和狒狒克里斯已经在乌代兰探索了一段时间。他们意识到它由n个城镇组成，编号从1到n。
乌代兰有n条定向道路。他们中的第i个从城镇i到另一个城镇ai（ai≠i）。ZS编码器可以翻转乌代兰任何道路的方向，即，如果在翻转之前从A镇到B镇，则在翻转之后从B镇到A镇。
ZS编码员认为，如果有一系列不同的城镇A1、A2、，。。。，Ak（k>1），使得每1≤i<k有一条从城镇Ai到城镇Ai+1的道路，以及从城镇Ak到城镇A1的另一条道路。换言之，如果其中一些道路形成了一些城镇的定向循环，那么这些道路就会令人困惑。
现在，编码者ZS想知道，在初始配置中，他可以选择翻转多少组道路（有2n个变体），以便在翻转组中的每条道路一次之后，生成的网络不会令人困惑。
请注意，翻转后，允许从某个城镇（可能是一些没有道路的城镇）或任何一对城市之间存在多条道路。
输入格式
输入的第一行包含单个整数n（2≤n≤2105）——乌代兰的城镇数量。
下一行包含n个整数a1，a2，。。。，an（1≤ai≤n，ai≠i），ai表示从镇i到镇ai的道路。
下一行包含n个整数a1，a2，。。。，an（1≤ai≤n，ai≠i），ai表示从镇i到镇ai的道路。
输出格式
打印一个整数，即翻转某组道路的方法数，以便生成的整组道路不会混淆。由于这个数字可能太大，请以模109+7打印答案
输入样例 复制
3
2 3 1输出样例 复制
6数据范围与提示
考虑第一个示例案例。有3个城镇和3条道路。城镇编号从1到3，道路最初编号为。按此顺序对道路1至3进行编号。
编码者ZS可以翻转的道路集（为了使它们不混淆）是{1}、{2}、{3}、{1,2}、{1,3}、{2,3}。请注意，空集是无效的，因为如果没有道路被翻转，那么城镇1、2、3将形成一个有向循环，因此它很混乱。同样，翻转所有道路也令人困惑。因此，编码器总共可以翻转6个可能的集合ZS。
样本图像显示了从第一个样本定向道路的所有可能方式，以使网络不会混淆。
编码者ZS可以翻转的道路集（为了使它们不混淆）是{1}、{2}、{3}、{1,2}、{1,3}、{2,3}。请注意，空集是无效的，因为如果没有道路被翻转，那么城镇1、2、3将形成一个有向循环，因此它很混乱。同样，翻转所有道路也令人困惑。因此，编码器总共可以翻转6个可能的集合ZS。
样本图像显示了从第一个样本定向道路的所有可能方式，以使网络不会混淆。