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<cmath>
#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1000100,P=1e9+7;
inline int read(){
	int x=0,f=0,c=getchar();
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+c-'0';return f?-x:x;
}
inline int ksm(int x,int y){
	int z=1;for(;y;y>>=1,x=1ll*x*x%P)
	if(y&1)z=1ll*z*x%P;return z;
}
int q[N],r,n,a[N],du[N],f[N],ans,s[N],fac[N],inv[N],pw[N],ipw[N];
void dfs(int x){du[x]--;q[++r]=x;if(du[a[x]])dfs(a[x]);}
inline int C(int n,int m){return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
int main(){
	int i,l,x,la,fr,re;
	n=read();ans=1;
	for(i=1;i<=n;i++)a[i]=read(),du[a[i]]++;
	for(i=1;i<=n;i++){
		if(!du[i])q[++r]=i;
		if(du[i]>2)goto fuck;
	}
	for(l=1;l<=r;l++){
		x=q[l];if(f[a[x]])goto fuck;
		f[a[x]]=f[x]+1;if(!(--du[a[x]]))q[++r]=a[x];
	}
	for(l=1;l<=n;l++)if(du[l]){
		r=la=0;dfs(l);re=1;
		for(i=1;i<=r;i++)
		if(f[x=q[i]]){
			if(!la){fr=la=i;continue;}
			if(i-la<f[x])goto fuck;
			if(i-la>f[x])re=(re+re)%P;la=i;
		}
		if(!la){s[r]++;continue;}
		x=q[fr];fr=fr+r;
		if(fr-la<f[x])goto fuck;
		if(fr-la>f[x])re=(re+re)%P;
		ans=1ll*ans*re%P;
	}
	fac[0]=inv[0]=pw[0]=ipw[0]=1;
	pw[1]=2;ipw[1]=(P+1)/2;
	for(i=1;i<=n;i++){
		fac[i]=1ll*fac[i-1]*i%P;
		inv[i]=ksm(fac[i],P-2);
		pw[i]=1ll*pw[i-1]*pw[1]%P;
		ipw[i]=1ll*ipw[i-1]*ipw[1]%P;
	}
	for(l=1;l<=n;l++)if(s[l]){
		re=0;for(i=0;i+i<=s[l];i++){
			x=1ll*C(s[l],i+i)*fac[i+i]%P*inv[i]%P*ipw[i]%P*ksm(l,i)%P;
			if(l>1&&(l&1)){x=1ll*x*pw[s[l]-i-i]%P;}re=(re+x)%P;
		}ans=1ll*ans*re%P;
	}printf("%d\n",ans);
	return 0;fuck:puts("0");;
}