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>
typedef long long i64;
const int N=100007,P=1e9+7;
int n,fa[N],in[N],q[N],ql=0,qr=0,md[N],ss[N][2],t[N];
i64 pw2[N],fac[N],fiv[N],ans=1;
i64 pw(i64 a,i64 n){
	i64 v=1;
	for(;n;n>>=1,a=a*a%P)if(n&1)v=v*a%P;
	return v;
}
int main(){
	scanf("%d",&n);
	for(int i=pw2[0]=1;i<=n;++i)pw2[i]=pw2[i-1]*2%P;
	for(int i=fac[0]=1;i<=n;++i)fac[i]=fac[i-1]*i%P;
	fiv[n]=pw(fac[n],P-2);
	for(int i=n;i;--i)fiv[i-1]=fiv[i]*i%P;
	for(int i=1;i<=n;++i)scanf("%d",fa+i),++in[fa[i]];
	for(int i=1;i<=n;++i)if(!in[i])q[++qr]=i;
	while(ql!=qr){
		int w=q[++ql],f=fa[w];
		if(md[f])return puts("0"),0;
		md[f]=md[w]+1;
		if(!--in[f])q[++qr]=f;
	}
	for(int i=1;i<=n;++i)if(in[i]){
		int c=0,sp=0;
		for(int w=i;in[w];in[w]=0,w=fa[w]){
			++c;
			if(md[w])ss[++sp][0]=md[w],ss[sp][1]=c;
		}
		if(sp){
			ss[0][1]=ss[sp][1]-c;
			for(int j=1;j<=sp;++j){
				int d=ss[j][1]-ss[j-1][1],d0=ss[j][0];
				if(d<d0)return puts("0"),0;
				if(d>d0)ans=ans*2%P;
			}
		}else ++t[c];
	}
	for(int i=1;i<=n;++i)if(t[i]){
		i64 s1=1,s2=0;
		if(i>1&&(i&1))
		for(int j=0,c=t[i];j<=c;j+=2){
			s2=(s2+s1*pw2[c-j]%P*fiv[j/2])%P;
			s1=i64(c-j)*(c-j-1)/2%P*s1%P*i%P;
		}
		else
		for(int j=0,c=t[i];j<=c;j+=2){
			s2=(s2+s1*fiv[j/2])%P;
			s1=i64(c-j)*(c-j-1)/2%P*s1%P*i%P;
		}
		ans=ans*s2%P;
	}
	printf("%lld\n",ans);
	return 0;
}