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>
#define mod 1000000007
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
int a[100010],p[100010],cir[100010],CIR,vis[100010];
int L[100010],D[100010],c[100010];
int fact[100010],ifact[100010],f[100010];
int C(int n,int m){return 1ll*fact[n]*ifact[m]%mod*ifact[n-m]%mod;}
int main(){
#ifdef XZZSB
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi();
	for(int i=1;i<=n;++i)a[i]=gi();
	int ans=1;
	for(int i=1;i<=n;++i)
		if(!vis[i]){
			int j;
			for(j=i;!vis[j];j=a[j])vis[j]=i;
			if(vis[j]==i){
				++CIR;
				while(!cir[j])cir[j]=CIR,j=a[j];
			}
		}
	for(int i=1;i<=n;++i)
		if(!cir[i]){
			if(p[a[i]])return puts("0"),0;
			p[a[i]]=i;
		}
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;++i)
		if(cir[i]&&!vis[cir[i]]){
			vis[cir[i]]=1;
			int m=0,id=0,j=i;
			do{
				++id;
				if(p[j]){
					L[++m]=id;D[m]=0;
					for(int o=p[j];o;o=p[o])++D[m];
				}
			}while(j=a[j],j!=i);
			if(m){
				L[0]=L[m]-id,D[0]=D[m];
				for(int j=1;j<=m;++j)
					if(L[j]-L[j-1]>D[j])ans=2*ans%mod;
					else if(L[j]-L[j-1]<D[j])return puts("0"),0;
			}else ++c[id];
		}
	fact[0]=1;for(int i=1;i<=n;++i)fact[i]=1ll*fact[i-1]*i%mod;
	ifact[n]=pow(fact[n],mod-2);for(int i=n;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	f[0]=1;for(int i=1;i*2<=n;++i)f[i]=1ll*(2*i-1)*f[i-1]%mod;
	for(int i=1;i<=n;++i){
		int res=0;
		for(int j=0;j*2<=c[i];++j)
			res=(res+1ll*C(c[i],2*j)*f[j]%mod*pow(i,j)%mod*((i>1&&(i&1))?pow(2,c[i]-2*j):1))%mod;
		ans=1ll*ans*res%mod;
	}
	printf("%d\n",ans);
	return 0;
}