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>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100000+10,mo=1000000007;
int f[maxn],g[maxn],num[maxn],a[maxn],h[maxn],go[maxn],nxt[maxn],d[maxn];
int bz[maxn];
int i,j,k,l,r,s,t,n,m,tot,ans;
bool czy;
void add(int x,int y){
	go[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
}
bool pd(int x){
	if (d[x]>1) return 0;
	bz[x]=1;
	if (!d[x]) return 1;
	int t=h[x];
	bool gjx=pd(go[t]);
	g[x]=g[go[t]]+1;
	return gjx;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d",&a[i]);
		d[a[i]]++;
		if (d[a[i]]>2){
			printf("0\n");
			return 0;
		}
		add(a[i],i);
	}
	ans=1;
	fo(i,1,n)
		if (!bz[i]){
			j=i;
			while (!bz[j]){
				bz[j]=1;
				j=a[j];
			}
			while (bz[j]==1){
				bz[j]=2;
				j=a[j];
			}
			k=j;
			czy=1;
			s=0;
			while (1){
				s++;
				if (d[j]>1){
					czy=0;
					t=h[j];
					while (t){
						if (bz[go[t]]!=2){
							l=go[t];
							break;
						}
						t=nxt[t];
					}
					if (!pd(l)){
						printf("0\n");
						return 0;
					}
					g[j]=g[l]+1;
				}
				j=a[j];
				if (j==k) break;
			}
			if (czy){
				num[s]++;
				continue;
			}
			while (d[j]==1) j=a[j];
			k=j;s=0;
			while (1){
				j=a[j];
				s++;
				if (d[j]>1){
					if (g[j]>s){
						printf("0\n");
						return 0;
					}
					else if (g[j]<s) ans=(ll)ans*2%mo;
					s=0;
				}
				if (j==k) break;
			}
		}
	fo(i,1,n){
		if (i==1) k=1;
		else if (i%2==1) k=2;
		else k=1;
		f[0]=1;
		fo(j,1,num[i]){
			f[j]=(ll)f[j-1]*k%mo;
			if (j>=2) (f[j]+=(ll)f[j-2]*(j-1)%mo*i%mo)%=mo;
		}
		ans=(ll)ans*f[num[i]]%mo;
	}
	(ans+=mo)%=mo;
	printf("%d\n",ans);
}