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;
const int mod = 1e9+7;
int ad(int x,int y) { x+=y; return x>=mod?x-mod:x; }
int sb(int x,int y) { x-=y; return x<0?x+mod:x; }
int mu(int x,int y) { return 1ll*x*y%mod; }
void up(int &x,int y) { x+=y; if(x>=mod)x-=mod; }
int ksm(int a,int b) {
	int ans = 1;
	for(;b;b>>=1,a=mu(a,a))
		if(b&1) ans=mu(ans,a);
	return ans;
}
int n;
const int maxn = 2e5+5;
int a[maxn],rd[maxn],from[maxn],f[maxn];
bool vis[maxn];
int ans = 1;
int CR[maxn],cnt;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		rd[a[i]]++;
	}
	for(int i=1;i<=n;i++) {
		if(rd[i]>2) { puts("0"); return 0; }
		else if(rd[i]<2||vis[i]) continue;
		int p = i;
		do{
			if(vis[p]) { puts("0"); return 0; }
			vis[p] = 1; from[a[p]] = p;
			p = a[p];
		}while(p!=i);
	}
	for(int i=1;i<=n;i++) {
		if(!rd[i]) {
			int p = i; int l1 = 0; int l2 = 0;
			while(!vis[p]) vis[p] = 1 , l1++ , p = a[p];
			do{
				l2++; p = from[p];
			}while(rd[p]!=2);
			if(l1==l2) continue;
			else if(l1<l2) ans = mu(ans,2);
			else { puts("0"); return 0; }
		}
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			int p = i; int cd = 0;
			do{
				p = a[p];
				cd++;
				vis[p] = 1;
			}while(p!=i);
			CR[++cnt] = cd;
		}
	}
	sort(CR+1,CR+1+cnt);
	for(int i=1,j;i<=n;i=j+1) {
		j = i;
		while(j<n&&CR[j+1]==CR[i]) j++;
		f[i-1] = 1;
		for(int k=i;k<=j;k++) {
			f[k] = f[k-1];
			if(CR[i]>1&&(CR[i]&1)) up(f[k],f[k-1]);
			if(k!=i) up(f[k],mu(f[k-2],mu(k-i,CR[i]) ) );
		}
		ans = mu(ans,f[j]);
	}
	printf("%d",ans);
	
}