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 RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int mod=1e9+7,N=100005;
int n,ans;
int a[N],du[N],cir[N],vis[N],footL[N],sum[N],f[N];
int qm(int x) {return x>=mod?x-mod:x;}
void workcir(int x) {
	int now=0,fr=0,ed=0,frL=0;
	while(cir[x]) {
		++now,cir[x]=0;
		if(footL[x]) {
			if(!fr) ed=fr=now,frL=footL[x];
			else {
				int kl=(footL[x]<now-ed)+(footL[x]<=now-ed);
				ans=1LL*ans*kl%mod,ed=now;
			}
		}
		x=a[x];
	}
	if(!fr) ++sum[now];
	else {
		int kl=(frL<now-ed+fr)+(frL<=now-ed+fr);
		ans=1LL*ans*kl%mod;
	}
}
void work() {
	for(RI i=1;i<=n;++i) {
		if(du[i]) continue;
		int x=i,len=0;while(!cir[x]) x=a[x],++len;
		footL[x]=len;
	}
	ans=1;
	for(RI i=1;i<=n;++i) if(cir[i]) workcir(i);
	//cout<<ans<<endl;
	for(RI i=1;i<=n;++i) {
		if(!sum[i]) continue;
		f[0]=1;
		for(RI j=1;j<=sum[i];++j) {
			if(i>1&&(i&1)) f[j]=qm(f[j-1]+f[j-1]);
			else f[j]=f[j-1];
			if(j>1) f[j]=qm(f[j]+1LL*f[j-2]*(j-1)%mod*i%mod);
		}
		ans=1LL*ans*f[sum[i]]%mod;
	}
}
int main()
{
	n=read();
	for(RI i=1;i<=n;++i) a[i]=read(),++du[a[i]];
	for(RI i=1;i<=n;++i) {
		if(vis[i]) continue;
		int x=i;while(!vis[x]) vis[x]=i,x=a[x];
		if(vis[x]!=i) continue;
		while(!cir[x]) cir[x]=1,x=a[x];
	}
	for(RI i=1;i<=n;++i)
		if((cir[i]&&du[i]>2)||(!cir[i]&&du[i]>1)) {puts("0");return 0;}
	work();
	printf("%d\n",ans);
	return 0;
}