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;
#define ll long long
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<class T> inline void read(T &n){
	char ch=GC;T w=1,x=0;
	while(!isdigit(ch)){if(ch=='-') w=-1;ch=GC;}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=GC;}
	n=x*w;
}
const int maxn=200005;
int n,a[maxn],deg[maxn];
int vis[maxn],isc[maxn],link[maxn];
int cnt[maxn],ans=1;
const int mod=1e9+7;
inline int add(int x,int y){
	x+=y;return x>=mod?x-mod:x;
}
inline int mul(int x,int y){
	return 1ll*x*y%mod;
}
void solve(int x){
	int now=0,fir=0,firl=0,lst=0;
	for(;isc[x];x=a[x]){
		now++,isc[x]=0;
		if(link[x]){
			if(!fir) fir=lst=now,firl=link[x];
			else{
				int tmp=now-lst;
				if(tmp<link[x]) puts("0"),exit(0);
				if(tmp>link[x]) ans=add(ans,ans);
				lst=now;
			}
		}
	}
	if(!fir) cnt[now]++;
	else{
		int tmp=fir+now-lst;
		if(tmp<firl) puts("0"),exit(0);
		if(tmp>firl) ans=add(ans,ans);
	}
}
int f[maxn]={1};
int main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),deg[a[i]]++;
	for(int i=1,j;i<=n;i++){
		if(vis[i]) continue;
		for(j=i;!vis[j];j=a[j]) vis[j]=i;
		if(vis[j]!=i) continue;
		for(;!isc[j];j=a[j]) isc[j]=1;
	}
	for(int i=1;i<=n;i++)
		if((isc[i]&&deg[i]>2)||(!isc[i]&&deg[i]>1)) puts("0"),exit(0);
	for(int i=1,j;i<=n;i++){
		if(deg[i]) continue;
		int len=0;
		for(j=i;!isc[j];j=a[j]) len++;
		link[j]=len;
	}
	for(int i=1;i<=n;i++) if(isc[i]) solve(i);
	for(int i=1;i<=n;i++){
		if(!cnt[i]) continue;
		int flag=((i>1)&&(i&1));
		for(int j=1;j<=cnt[i];j++){
			flag?f[j]=add(f[j-1],f[j-1]):f[j]=f[j-1];
			if(j>1) f[j]=add(f[j],mul(f[j-2],mul(j-1,i)));
		}
		ans=mul(ans,f[cnt[i]]);
	}
	cout<<ans<<endl;
	return 0;
}