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>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,i,j,zz[100005],x,sum[100005],book[100005],book2[100005];
long long top2,sum2,zhan[100005],zhan2[100005],book3[100005],ans;
long long jc[100005],ny[100005],flag;
long long top,nex[100005],to[100005],fir[100005];
void lj(int u,int v){
	top++;
	nex[top]=fir[u];
	fir[u]=top;
	to[top]=v;
}
int ss(int v){
	int sum3=0;
	sum[v]=1-book2[v];
	for(int top1=fir[v];top1;top1=nex[top1])
		if(book2[to[top1]]==0){
			sum[v]+=ss(to[top1]);
			sum3++;
		}
	if(sum3>=2)
		flag=1;
	return sum[v];
}
long long ksm(long long u,long long v){
	long long o=1;
	while(v){
		if(v&1)
			o=o*u%mo;
		u=u*u%mo;
		v>>=1;
	}
	return o;
}
long long C(long long u,long long v){
	return jc[u]*ny[v]%mo*ny[u-v]%mo;
}
int main(){
	n=read();
	for(i=1;i<=n;i++){
		zz[i]=read();
		lj(zz[i],i);
	}
	jc[0]=1;
	for(i=1;i<=n;i++)
		jc[i]=jc[i-1]*i%mo;
	ny[n]=ksm(jc[n],mo-2);
	for(i=n-1;i>=0;i--)
		ny[i]=ny[i+1]*(i+1)%mo;
	for(i=1;i<=n;i++)
		if(book[i]==0){
			x=i;
			while(book[x]==0){
				book[x]=i;
				x=zz[x];
			}
			if(book[x]==i){
				while(book2[x]==0){
					book2[x]=1;
					x=zz[x];
				}
			}
		}
	ans=1;
	for(i=1;i<=n;i++)
		if(book2[i]==1)
			ss(i);
	if(flag==1){
		pus(0,2);
		return 0;
	}
	for(i=1;i<=n;i++)
		if(book2[i]==1){
			x=i;sum2=0;top2=0;
			while(book2[x]!=2){
				book2[x]=2;
				sum2++;
				if(sum[x]!=0){
					top2++;
					zhan[top2]=sum[x];
					zhan2[top2]=sum2;
				}
				x=zz[x];
			}
			if(top2!=0){
				zhan[top2+1]=zhan[1];
				zhan2[top2+1]=zhan2[1]+sum2;
				for(j=1;j<=top2;j++)
					if(zhan[j+1]<zhan2[j+1]-zhan2[j])
						ans=ans*2%mo;
					else if(zhan[j+1]>zhan2[j+1]-zhan2[j])
						ans=0;
			}
			else
				book3[sum2]++;
		}
	for(j=1;j<=n;j++){
		sum2=0;
		for(i=0;(i<<1)<=book3[j];i++)
			if((j&1)&&j!=1)
				sum2=(sum2+C(book3[j],i<<1)*jc[i<<1]%mo*ny[i]%mo*ksm(ksm(2,i),mo-2)%mo*ksm(j,i)%mo*ksm(2,book3[j]-(i<<1)))%mo;
			else
				sum2=(sum2+C(book3[j],i<<1)*jc[i<<1]%mo*ny[i]%mo*ksm(ksm(2,i),mo-2)%mo*ksm(j,i))%mo;
		ans=ans*sum2%mo;
	}
	pus(ans,2);
	return 0;
}