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;
const int maxn=100010,mod=1000000007,inv2=500000004;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,a[maxn],deg[maxn],ans=1,stk[maxn],tp,q[maxn],h,r,len[maxn],seq[maxn],tot,cnt[maxn];
int fac[maxn],inv[maxn],invfac[maxn];
bool vis[maxn],ins[maxn],cyc[maxn];
void dfs(int u){
	if(vis[u]){
		if(ins[u]){
			ROF(i,tp,1){
				cyc[stk[i]]=true;
				if(stk[i]==u) break;
			}
		}
		return;
	}
	vis[u]=ins[u]=true;
	stk[++tp]=u;
	dfs(a[u]);
	ins[u]=false;
}
bool dfs2(int u){
	if(vis[u]) return true;
	vis[u]=true;
	seq[++tot]=len[u];
	return dfs2(a[u]) && !len[u];
}
inline int C(int n,int m){
	return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int main(){
	n=read();
	FOR(i,1,n) a[i]=read(),deg[a[i]]++;
	FOR(i,1,n) dfs(i);
	FOR(i,1,n) if(cyc[i] && deg[i]>=3|| !cyc[i] && deg[i]>=2) return puts("0"),0;
	h=1;r=0;
	FOR(i,1,n) if(!deg[i]) q[++r]=i;
	while(h<=r){
		int u=q[h++];
		len[a[u]]=len[u]+1;
		if(!cyc[a[u]]) q[++r]=a[u];
	}
	MEM(vis,0);
	FOR(i,1,n) if(cyc[i] && !vis[i]){
		tot=0;
		if(dfs2(i)) cnt[tot]++;
		else{
			int pre=0;
			FOR(j,1,tot) if(seq[j]){
				if(pre){
					int at=j-seq[j];
					if(at<pre) return puts("0"),0;
					if(at>pre && tot>=2) ans=2*ans%mod;
				}
				pre=j;
			}
			FOR(j,1,tot) if(seq[j]){
				int at=j-seq[j]+tot;
				if(at<pre) return puts("0"),0;
				if(at>pre && tot>=2) ans=2*ans%mod;
				break;
			}
		}
	}
	fac[0]=fac[1]=inv[1]=invfac[0]=invfac[1]=1;
	FOR(i,2,n){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
		invfac[i]=1ll*invfac[i-1]*inv[i]%mod;
	}
	FOR(i,1,n) if(cnt[i]){
		int s=0;
		FOR(j,0,cnt[i]/2){
			int x=1ll*C(cnt[i],2*j)*C(2*j,j)%mod*fac[j]%mod;
			if(j) x=1ll*x*qpow(inv2,j)%mod*qpow(i,j)%mod;
			if(i%2==1 && i!=1) x=1ll*x*qpow(2,cnt[i]-2*j)%mod;
			s=(s+x)%mod;
		}
		ans=1ll*ans*s%mod;
	}
	printf("%d\n",ans);
}