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 sz=1e5+7;
const int mod=1e9+7;
int n;
int T;
int ans;
int cnt;
bool flag;
int b[sz];
int a[sz],r[sz],rr[sz];
int t[sz],rt[sz];
int qp[sz],_qp[sz];
int inv[sz],fac[sz],_fac[sz];
int del[sz],dep[sz];
queue<int>q;
void upd(int &x,int y){
	x=x+y>=mod?x+y-mod:x+y;
}
int qpow(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*x*ret%mod;
	return ret;
}
void find(int x){
	if(dep[x]) flag=0;
	cnt++;
	del[x]=1;
	if(!del[a[x]]) find(a[x]);
	b[a[x]]=x;
}
void init(){
	qp[0]=_qp[0]=1;
	fac[0]=_fac[0]=1;
	inv[1]=fac[1]=_fac[1]=1;
	for(int i=2;i<sz;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		fac[i]=1ll*i*fac[i-1]%mod;
		_fac[i]=1ll*inv[i]*_fac[i-1]%mod;
	}
	for(int i=1;i<sz;i++){
		qp[i]=2ll*qp[i-1]%mod;
		_qp[i]=1ll*inv[2]*_qp[i-1]%mod;
	}
}
void build(){
	for(int i=1;i<=n;i++) if(!r[i]) q.push(i);
	while(!q.empty()){
		int x=q.front();
		dep[a[x]]=dep[x]+1;
		r[a[x]]--;
		if(!r[a[x]]) q.push(a[x]);
		del[x]=1;
		q.pop();
	}
	for(int i=1;i<=n;i++){
		if(del[i]==1&&rr[i]>1) { printf("0\n"); exit(0); }
		if(del[i]==0&&rr[i]>2) { printf("0\n"); exit(0); }
	}
	for(int i=1;i<=n;i++)
	if(!del[i]){
		cnt=0;
		flag=1;
		find(i);
		if(flag) t[cnt]++;
		else{
			int x=i;
			while(!dep[x]) x=b[x];
			rt[++T]=x;
		}
	}
}
void dfs(int x,int res){
	if(dep[x]){
		if(res>0) ans=0;
		if(res<0) ans=2ll*ans%mod;
		res=dep[x];
	}
	if(!del[x]) return;
	del[x]=0;
	dfs(b[x],res-1);
}
int main(){
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),r[a[i]]++,rr[a[i]]++;
	build();
	ans=1;
	for(int i=1;i<=n;i++){
		if(!t[i]) continue;
		int sum=0;
		for(int j=0;j<=t[i];j+=2){
			int tot;
			tot=1ll*fac[t[i]]*_fac[t[i]-j]%mod*_fac[j/2]%mod*_qp[j/2]%mod*qpow(i,j/2)%mod;
			if(i%2==1&&i>1) tot=1ll*tot*qp[t[i]-j]%mod;
			upd(sum,tot);
		}
		ans=1ll*ans*sum%mod;
	}
	for(int i=1;i<=T;i++) dfs(rt[i],0);
	printf("%d\n",ans);
}