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 N 100005
#define LL long long
using namespace std;
const int mo=1e9+7,I2=(mo+1)/2;
vector<int> G[N],E[N];
int n,a[N],ufs[N],g[N],d[N],c[N],w[N],lw,vis[N],nu[N],ans=1,cnt,tot,L[N],X[N],cir[N],fc[N],xf[N],f[N];
LL fpm(LL x,LL y){ LL s=1; while(y){ if(y&1) s=(s*x)%mo; y>>=1,x=(x*x)%mo;} return s;}
LL C(int n,int m){ return 1LL*fc[n]*xf[m]%mo*xf[n-m]%mo;}
int find(int x){ return ufs[x] ? ufs[x]=find(ufs[x]) : x;}
void dfs(int t)
{
	int i; vis[t]=1,w[++lw]=t;
	for(i=0;i<G[t].size();i++)
		if(!vis[G[t][i]]) dfs(G[t][i]);
}
int DFS(int t)
{
	int i,cnt=0;
	for(i=0;i<E[t].size();i++)
		if(!cir[E[t][i]]) cnt++;
	if(cnt>1) ans=0;
	for(i=0;i<E[t].size();i++)
		if(!cir[E[t][i]]) return DFS(E[t][i])+1;
	return 0;
}
void solve(int t)
{
	int i,j,x,y,z;
	lw=cnt=0,dfs(t);
	for(i=1;i<=lw;i++)
		if(d[w[i]]&1) break;
	if(i>lw){ c[lw]++; return ;}
	for(i=1;i<=lw;i++)
		for(j=0;j<E[w[i]].size();j++){
			if(find(E[w[i]][j])==find(w[i])) y=w[i],x=E[w[i]][j];
			else ufs[E[w[i]][j]]=w[i];
		  }
	tot=0,cir[x]=cir[y]=1;
	for(i=y;i!=x;i=a[i]) cir[i]=1;
	for(i=y;i!=x;i=a[i]){
		nu[i]=++cnt,z=DFS(i);
		if(z) ++tot,L[tot]=z,X[tot]=cnt;
	  }
	nu[x]=++cnt,z=DFS(x);
	if(z) ++tot,L[tot]=z,X[tot]=cnt;
	for(i=2;i<=tot;i++){
		if(L[i]>X[i]-X[i-1]) ans=0;
		if(L[i]<X[i]-X[i-1]) ans=(ans+ans)%mo;
	  }
	if(L[1]>X[1]+cnt-X[tot]) ans=0;
	if(L[1]<X[1]+cnt-X[tot]) ans=(ans+ans)%mo;
}
void dp(int t)
{
	int i,sum=0,pw=1;
	if(t%2==1&&t>1)
		for(i=1;i<=c[t];i++) pw=(pw*2)%mo;
	for(i=0;i*2<=c[t];i++){
		sum=(sum+C(c[t],2*i)*pw%mo*f[i]%mo)%mo,pw=1LL*pw*t%mo;
		if((t&1)&&t>1) pw=1LL*pw*I2%mo*I2%mo;
	  }
	ans=1LL*ans*sum%mo;
}
int main()
{
	int i;
	scanf("%d",&n),fc[0]=xf[0]=f[0]=1;
	for(i=1;i<=n;i++){
		fc[i]=1LL*fc[i-1]*i%mo;
		xf[i]=fpm(fc[i],mo-2);
		f[i]=f[i-1]*(2LL*i-1)%mo;
	  }
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		G[a[i]].push_back(i);
		G[i].push_back(a[i]);
		E[a[i]].push_back(i);
		d[i]++,d[a[i]]++;
	  }
	for(i=1;i<=n;i++)
		if(d[i]>=4){ printf("0"); return 0;}
	for(i=1;i<=n;i++){
		if(vis[i]) continue;
		solve(i);
	  }
	for(i=1;i<=n;i++) dp(i);
	cout<<ans;
	return 0;
}