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>
using namespace std;
#define mo 1000000007ll
#define N 100010
#define int long long
int n,d[N],a[N],vi[N],c[N],le[N],s[N],f[N],ans;
void dfs(int x){
	int v=0,y=0,z=0,p=0;
	while(c[x]){
		v++;
		c[x]=0;
		if(le[x]){
			if(!y){
				z=y=v;
				p=le[x];
			}
			else{
				ans=ans*((le[x]<v-z)+(le[x]<=v-z))%mo;
				z=v;
			}
		}
		x=a[x];
	}
	if(!y)s[v]++;
	else ans=ans*((p<v-z+y)+(p<=v-z+y))%mo;
}
void dp(){
	for(int i=1;i<=n;i++){
		if(d[i])continue;
		int x=i,l=0;
		while(!c[x]){
			x=a[x];
			l++;
		}
		le[x]=l;
	}
	ans=1;
	for(int i=1;i<=n;i++)
		if(c[i])dfs(i);
	for(int i=1;i<=n;i++)
		if(s[i]){
			f[0]=1;
			for(int j=1;j<=s[i];j++){
				if(i>1&&(i&1))
					f[j]=f[j-1]*2ll%mo;
				else f[j]=f[j-1];
				if(j>1)f[j]=(f[j]+f[j-2]*(j-1)%mo*i%mo)%mo;
			}
			ans=ans*f[s[i]]%mo;
		}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(vi[i])continue;
		int x=i;
		while(!vi[x]){
			vi[x]=i;
			x=a[x];
		}
		if(vi[x]!=i)continue;
		while(!c[x]){
			c[x]=1;
			x=a[x];
		}
	}
	for(int i=1;i<=n;i++)
		if((c[i]&&d[i]>2)||(!c[i]&&d[i]>1)){
			puts("0");
			return 0;
		}
	dp();
	cout<<ans;
}