Problem: You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?

* For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.



Find the count modulo 10^9 + 7.

Constraints

* 1 ≤ N ≤ 10^5
* a_i is an integer.
* 1 ≤ a_i ≤ N

Input

The input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Examples

Input

3
1 2 3


Output

4


Input

2
1 1


Output

1


Input

3
2 1 1


Output

2


Input

3
1 1 1


Output

0


Input

13
2 1 4 3 6 7 5 9 10 8 8 9 11


Output

6

Solution (in CPP):

Solution:
//============================================================================
// Author       : Sun YaoFeng
//============================================================================

//#pragma 	comment(linker, "/STACK:100240000,100240000")
//#include	<cstdio>
//#include	<cstdlib>
//#include	<cstring>
//#include	<algorithm>

#include	<bits/stdc++.h>

using	namespace	std;

#define DB		double
#define	lf		else if
#define I64		long long
#define	Rd()	(rand()<<15|rand())
#define For(i,a,b)	for(int i=a,lim=b;i<=lim;i++)
#define Rep(i,a,b)	for(int i=a,lim=b;i>=lim;i--)

#define	fi	first
#define se	second
#define MK	make_pair
#define pb	push_back
#define PA	pair<int, int>

//#define	min(a,b)	((a)<(b)?(a):(b))
//#define	max(a,b)	((a)<(b)?(b):(a))

#define	CH	(ch=getchar())
int		IN()	{
		int x= 0, f= 0, ch;
		for	(; CH < '0' || ch > '9';)	f= (ch == '-');
		for	(; ch >= '0' && ch <= '9'; CH)	x= x*10 + ch -'0';
		return	f? -x : x;
}

#define n	200005
#define P	1000000007

int		N, L[n], R[n];

int		A[n], B[n], S[n], V[n], Q[n], G[n], Deg[n], Now[n], Siz[n];

int		Pow(int a,int b){
		int ret=1;
		for (;b;b>>=1,a=1ll*a*a%P)
			if  (b&1)	ret=1ll*ret*a%P;
		return	ret;
}

int		C(int a, int b)	{
		return	1ll*L[a]*R[b]%P*R[a-b]%P;
}

int		main(int argc, char* argv[]){
		N= IN();
		
		L[0]= 1;
		For(i, 1, N)	L[i]= 1ll*L[i-1]*i%P;
		
		R[N]= Pow(L[N], P-2);
		Rep(i, N, 1)	R[i-1]= 1ll*R[i]*i%P;
		
		For(i, 1, N)	A[i]= IN(), Deg[A[i]]++, Siz[i]= 1;
		For(i, 1, N)	{
			Now[i]= Deg[i];
			if	(! Now[i])	Q[++ *Q]= i;
		}
		
		for (int i= 1; i <= *Q; i++)	{
			int u= Q[i], f= A[u];
			
			Siz[f]+= Siz[u];
			Now[f]--;
			
			if	(! Now[f])	Q[++ *Q]= f;
		}
		
		For(i, 1, *Q)	V[Q[i]]= 1;
		For(i, 1, N)	{
			if	(V[i] && Deg[i] > 1)	return	puts("0"), 0;
			if	(! V[i] && Deg[i] > 2)	return	puts("0"), 0;
		}
		
		int	Ans= 1;
		For(i, 1, N)	if	(! V[i])	{
			int j= i, len= 0;
			for (; ;)	{
				V[j]= 1;
				B[++ len]= Siz[j] - 1;
				
				j= A[j];
				if	(j == i)	break;
			}
			
			For(i, 1, len)	B[len + i]= B[i];
			For(i, 1, 2*len)	S[i]= S[i-1] + B[i];
			
			if	(! S[len])	{
				G[len]++;	continue;
			}
			if	(S[len] > len)	return	puts("0"), 0;
			
			int ret= 1;
			For(i, 1, len)	{
				int x= B[i], t= 0;
				if	(! x)	continue;
				
				if	(S[len+i-1] - S[len+i-x] == 0)	t++;
				if	(S[len+i-1] - S[len+i-x-1] == 0)	t++;
				
				ret= 1ll*ret*t%P;
			}
			
			Ans= 1ll*Ans*ret%P;
		}
		
	//	printf("%d\n", Ans);
		
		For(i, 1, N)	if	(G[i])	{
			int x= G[i], t= 1, v= (i > 1 && (i&1)) ? 2 : 1, ret= Pow(v, x);
			
			For(j, 1, x / 2)	{
				t= 1ll*t*C(x - (j-1)*2, 2)%P;
				ret= (ret + 1ll*t*R[j]%P*Pow(i, j)%P*Pow(v, x - 2*j))%P;
			}
			
			Ans= 1ll*Ans*ret%P;
		}
		
		printf("%d\n", Ans);
		
		return	0;
}