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<stdio.h>
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return(ll)a*b%mod;}
int a[100010],d[100010],p[100010],f[100010],c[100010];
bool v[100010];
int main(){
	int n,i,j,c1,c2,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",a+i);
		d[a[i]]++;
	}
	#define wrong {putchar('0');return 0;}
	ans=1;
	for(i=1;i<=n;i++){
		if(d[i]>2)wrong
		if(v[i]||d[i]<2)continue;
		j=i;
		do{
			if(v[j])wrong
			v[j]=1;
			p[a[j]]=j;
			j=a[j];
		}while(j!=i);
	}
	for(i=1;i<=n;i++){
		if(d[i]==0){
			c1=0;
			for(j=i;d[j]!=2;j=a[j]){
				c1++;
				v[j]=1;
			}
			c2=1;
			for(j=p[j];d[j]!=2;j=p[j])c2++;
			if(c1>c2)wrong
			if(c1<c2)ans=mul(ans,2);
		}
	}
	for(i=1;i<=n;i++){
		if(!v[i]){
			c1=0;
			j=i;
			do{
				v[j]=1;
				j=a[j];
				c1++;
			}while(j!=i);
			c[c1]++;
		}
	}
	for(i=1;i<=n;i++){
		c1=1+(i!=1&&(i&1));
		f[0]=1;
		f[1]=c1;
		for(j=2;j<=c[i];j++)f[j]=(mul(f[j-2],mul(j-1,i))+mul(f[j-1],c1))%mod;
		ans=mul(ans,f[c[i]]);
	}
	printf("%d",ans);
}