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 maxn=1e5+10,mod=1e9+7;
int n,a[maxn],cnt[maxn];
int dfsclock,dfn[maxn],low[maxn],stk[maxn],top,scccnt,scc[maxn],size[maxn];
ll ans,fac[maxn],inv[maxn],f[maxn],pow2[maxn];
int type[maxn],weight[maxn];
vector<int> g[maxn];

inline ll qpow(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1ll)
			res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
inline void init(){
	fac[0]=1;for(int i=1;i<maxn;++i)fac[i]=fac[i-1]*i%mod;
	inv[maxn-1]=qpow(fac[maxn-1],mod-2);for(int i=maxn-1;i;--i)inv[i-1]=inv[i]*i%mod;
	f[0]=1;for(int i=1;i<maxn;++i)f[i]=f[i-1]*(2*i-1)%mod;
	pow2[0]=1;for(int i=1;i<maxn;++i)pow2[i]=pow2[i-1]*2%mod;
}
void dfs(int pos){
	dfn[pos]=low[pos]=++dfsclock;
	stk[++top]=pos;
	if(!dfn[a[pos]]){
		dfs(a[pos]);
		low[pos]=min(low[pos],low[a[pos]]);
	}
	else if(!scc[a[pos]])
		low[pos]=min(low[pos],dfn[a[pos]]);
	if(dfn[pos]<=low[pos]){
		++scccnt;
		do{
			scc[stk[top]]=scccnt;
			++size[scccnt];
		}
		while(stk[top--]!=pos);
	}
}

int main(){
	init();
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			dfs(i);
	for(int i=1;i<=n;++i)
		if(scc[a[i]]==scc[i])
			type[scc[i]]=1;
		else
			g[a[i]].push_back(i),weight[scc[a[i]]]=true;
	for(int i=1;i<=n;++i)
		if(g[i].size()>1){
			puts("0");
			return 0;
		}
	for(int i=1;i<=scccnt;++i)
		if(type[i]==1){
			if(weight[i])
				type[i]=2;
			else
				++cnt[size[i]];
		}
	ans=1;
	for(int i=1;i<=n;++i)
		if(type[scc[i]]==2){
			type[scc[i]]=0;
			static int ring[maxn];
			int len;ll tmp=1;
			ring[len=1]=i;
			for(int p=a[i];p!=i;p=a[p])
				ring[++len]=p;
			for(int j=1;j<=len;++j)
				if(g[ring[j]].size()){
					int p=ring[j],val=0;
					while(g[p].size())
						++val,p=g[p][0];
					int nxt=1;
					for(int k=j==1?len:j-1;g[ring[k]].empty();k=k==1?len:k-1)
						++nxt;
					if(nxt>val)
						tmp=tmp*2%mod;
					if(nxt<val){
						puts("0");
						return 0;
					}
				}
			ans=ans*tmp%mod;
		}
	for(int i=1;i<=n;++i)
		if((i&1)&&i>1){
			ll tmp=0;
			for(int j=0;2*j<=cnt[i];++j)
				tmp=(tmp+fac[cnt[i]]*inv[2*j]%mod*inv[cnt[i]-2*j]%mod*f[j]%mod*qpow(i,j)%mod*pow2[cnt[i]-2*j])%mod;
			ans=ans*tmp%mod;
		}
		else{
			ll tmp=0;
			for(int j=0;2*j<=cnt[i];++j)
				tmp=(tmp+fac[cnt[i]]*inv[2*j]%mod*inv[cnt[i]-2*j]%mod*f[j]%mod*qpow(i,j))%mod;
			ans=ans*tmp%mod;
		}
	cout<<ans<<endl;
	return 0;
}