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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long fact[310000];
long long inv[310000];
long long finv[310000];
int p[110000];
int cnt[110000];
vector<int>g[110000];
vector<int>rev[110000];
int v[110000];
int cur;
int num[110000];
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		b/=2;a=a*a%mod;
	}
	return ret;
}
void dfs(int a){
	for(int i=0;i<g[a].size();i++){
		if(v[g[a][i]])continue;
		v[g[a][i]]=1;
		dfs(g[a][i]);
	}
	num[cur++]=a;
}
int scc[110000];
void dfs2(int a){
	scc[a]=cur;
	for(int i=0;i<rev[a].size();i++){
		if(v[rev[a][i]])continue;
		v[rev[a][i]]=1;
		dfs2(rev[a][i]);
	}
}
int dfs3(int a,int b){
	int ret=1;
	for(int i=0;i<rev[a].size();i++){
		if(b==scc[rev[a][i]])continue;
		ret+=dfs3(rev[a][i],b);
	}
	return ret;
}
int cy[110000];
int in[110000];
int out[110000];
int sz[110000];
int fi[110000];
 
int ren[110000];
 
long long dp[110000];
int main(){
	fact[0]=finv[0]=1;
	inv[1]=1;
	for(int i=1;i<310000;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	for(int i=2;i<310000;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<310000;i++){
		finv[i]=finv[i-1]*inv[i]%mod;
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);p[i]--;
		cnt[p[i]]++;
	}
	for(int i=0;i<a;i++)if(cnt[i]>2){
		printf("0\n");return 0;
	}
	for(int i=0;i<a;i++){
		g[i].push_back(p[i]);
		rev[p[i]].push_back(i);
	}
	for(int i=0;i<a;i++){
		if(v[i])continue;
		v[i]=1;
		dfs(i);
	}
	cur=0;
	for(int i=0;i<a;i++)v[i]=0;
	for(int i=a-1;i>=0;i--){
		if(v[num[i]])continue;
		v[num[i]]=1;
		fi[cur]=num[i];
		dfs2(num[i]);
		cur++;
	}
	for(int i=0;i<a;i++){
		in[scc[p[i]]]++;
		sz[scc[i]]++;
		if(scc[p[i]]!=scc[i])out[scc[i]]++;
	}
	for(int i=0;i<a;i++){
		if(cnt[i]>1&&scc[i]!=scc[p[i]]){
			printf("0\n");return 0;
		}
	}
	long long ret=1;
	for(int i=0;i<cur;i++){
		//printf("%d %d\n",in[i],sz[i]);
		if(out[i])continue;
		if(in[i]==sz[i]){
			cy[sz[i]]++;
			continue;
		}
		if(out[i])continue;
		vector<int>L;
		int at=fi[i];
		while(1){
			L.push_back(dfs3(at,scc[at])-1);
			at=p[at];
			if(at==fi[i])break;
		}
 
		int now=0;
		for(int j=0;j<L.size()*2;j++){
			ren[j%L.size()]=now;
			if(L[j%L.size()]==0)now++;
			else now=1;
		}
		for(int j=0;j<L.size();j++){
			if(L[j]==0)continue;
			if(ren[j]<L[j])ret*=0;
			else if(ren[j]>L[j])ret=ret*2%mod;
		}
	}
	for(int i=1;i<=a;i++){
		long long tmp=0;
		for(int j=0;j*2<=cy[i];j++){
 
			long long ks=pw(i,j)*fact[cy[i]]%mod*finv[cy[i]-j*2]%mod*finv[j]%mod*pw(500000004,j)%mod;
			if(i%2&&i!=1){
				ks=ks*pw(2,cy[i]-j*2)%mod;
			}
			tmp=(tmp+ks)%mod;
		}
		ret=ret*tmp%mod;
	}
	printf("%lld\n",ret);
}