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<cstdio>
const int MaxN=100010,mod=1000000007;
int N,a[MaxN];
struct edge{int to;edge*next;}E[MaxN],*fir[MaxN];
int C[MaxN],pos[MaxN],dep[MaxN],cnt[MaxN],ways[MaxN];
bool vis[MaxN];
int solve(){
	int res=1;
	for(int i=0;i<N;i++)if(!vis[i]){
		int len=0,tot=0,j=i,k;
		for(;!vis[j];j=a[j])vis[j]=1;
		for(k=i;vis[k];k=a[k])vis[k]=0;
		for(;!vis[j];j=a[j])vis[C[len++]=j]=1;
		for(j=0,k=len-1;j<k;j++,k--){
			int t=C[j];C[j]=C[k],C[k]=t;
		}
		for(j=0;j<len;j++){
			int x=C[j],d=0;
			for(;;){
				int c=0,t;
				for(edge*e=fir[x];e;e=e->next)if(!vis[e->to])c++,t=e->to;
				if(c>1)return 0;
				if(!c)break;
				vis[x=t]=1;d++;
			}
			if(d)pos[tot]=j,dep[tot++]=d;
		}
		if(tot){
			for(j=0;j<tot;j++){
				int d=(pos[(j+1)%tot]-pos[j])%len;
				if(d<=0)d+=len;
				if(d<dep[j])return 0;
				if(d>dep[j])res=res*2%mod;
			}
		}
		else cnt[len]++;
	}
	for(int i=1;i<=N;i++){
		ways[0]=1;
		for(int j=1;j<=cnt[i];j++){
			ways[j]=ways[j-1]*(i>1&&i%2?2:1)%mod;
			if(j>1)ways[j]=(ways[j]+(j-1ll)*ways[j-2]%mod*i)%mod;
		}
		res=1ll*res*ways[cnt[i]]%mod;
	}
	return res;
}
int main(){
	while(scanf("%d",&N)==1){
		for(int i=0;i<N;i++)scanf("%d",a+i),--a[i],fir[i]=0,vis[i]=0;
		for(int i=0;i<N;i++)E[i]=(edge){i,fir[a[i]]},fir[a[i]]=E+i;
		for(int i=N;i;i--)cnt[i]=0;
		printf("%d\n",solve());
	}
}