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:
#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MX=100105,md=1000000007;
int i,j,k;
int f[MX],fac[MX],facinv[MX],M[MX];

int pw(int x,int y){
	int z=1;
	for(;y;y>>=1,x=(LL)x*x%md)if(y&1)z=(LL)z*x%md;
	return z;
}
int C(int n,int m){return (LL)fac[n]*facinv[m]%md*facinv[n-m]%md;}
void ini(int n){
	int i;
	fac[0]=facinv[0]=f[0]=M[0]=1;
	for(i=1;i<=n;i++)M[i]=(M[i-1]+M[i-1])%md;
	for(i=1;i<=n;i++)f[i]=(LL)f[i-1]*(2*i-1)%md;
	for(i=1;i<=n;i++)fac[i]=(LL)fac[i-1]*i%md;
	facinv[n]=pw(fac[n],md-2);
	for(i=n-1;i;i--)facinv[i]=(LL)facinv[i+1]*(i+1)%md;
}
int n,m,ch,ff,ans;
int a[MX],b[MX],z[MX],fg[MX],num[MX],d[MX],dp[MX];
int cal(int n,int m){
	int i,k,ans=0;
	if((m&1)&& m>1){
		for(i=0,k=1;i+i<=n;i++,k=(LL)k*m%md)ans=((LL)f[i]*k%md*C(n,i+i)%md*M[n-i-i]%md+ans)%md;
	}else{
		for(i=0,k=1;i+i<=n;i++,k=(LL)k*m%md)ans=((LL)f[i]*k%md*C(n,i+i)%md+ans)%md;
	}
	return ans;
}
int main(){
	cin>>n;
	ini(n);
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)d[a[i]]++;
	for(i=1;i<=n;i++)if(!z[i]){
		for(j=i;z[j]!=i && !z[j];j=a[j])z[j]=i;
		if(z[j]==i){
			fg[j]=1;
			for(k=a[j];k!=j;k=a[k])fg[k]=1;
		}
	}
	for(i=1;i<=n;i++)if(d[i]>fg[i]+1)return cout<<0<<endl,0;
	for(i=1;i<=n;i++)if(!fg[i])b[a[i]]=i;
	for(i=1;i<=n;i++)if(fg[i]){
		for(j=b[i];j;j=b[j])dp[i]++;
	}
	memset(z,0,sizeof z);
	ans=1;
	for(i=1;i<=n;i++)if(!z[i] && fg[i]){ 
		int nm=0,Fg=0;
		for(j=i;!z[j];j=a[j]){
			z[j]=1;
			nm++;
			if(dp[j])Fg=j;
		}
		if(!Fg)num[nm]++;
		else {
			k=0;
			for(j=a[Fg];j!=Fg;j=a[j]){
				k++;
				if(dp[j]){
					if(dp[j]>k)ans=0;
					if(dp[j]<k)ans=(ans+ans)%md;
					k=0;
				}
			}
			k++;
			if(dp[Fg]>k)ans=0;
			if(dp[Fg]<k)ans=(ans+ans)%md;
		}
	}
	for(i=1;i<=n;i++)if(num[i])ans=(LL)ans*cal(num[i],i)%md;
	cout<<ans<<endl;
	return 0;
}