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>
#define ll long long
#define mod 1000000007
#define N 100009
using namespace std;

int n,a[N],fst[N],nxt[N],dgr[N],vis[N],num[N],f[N];
int main(){
	scanf("%d",&n);
	int i,j,k,sz,tmp,rst;
	for (i=1; i<=n; i++){
		scanf("%d",&a[i]);
		nxt[i]=fst[a[i]]; fst[a[i]]=i; dgr[a[i]]++;
	}
	int ans=1; bool flag;
	for (i=1; i<=n; i++) if (!vis[i]){
		for (j=i; !vis[j]; j=a[j]) vis[j]=1;
		sz=0; flag=1;
		for (; vis[j]!=2; j=a[j]){
			sz++; vis[j]=2;
			if (dgr[j]>2){ puts("0"); return 0; }
			else if (dgr[j]>1) flag=0;
		}
		if (flag){
			num[sz]++; continue;
		}
		for (; dgr[j]==1; j=a[j]); j=a[j];
		for (rst=0; vis[j]!=3; j=a[j]){
			vis[j]=3; rst++;
			for (k=fst[j]; k; k=nxt[k]) if (vis[k]<2){
				for (tmp=1; dgr[k]==1; k=fst[k]){
					vis[k]=1; tmp++;
				}
				vis[k]=1;
				if (dgr[k] || tmp>rst){ puts("0"); return 0; }
				if (rst>tmp) ans=(ans<<1)%mod;
				rst=0;
			}
		}
	}
	for (i=1; i<=n; i++){
		k=i>1 && (i&1)?2:1;
		for (j=f[0]=1; j<=num[i]; j++){
			f[j]=f[j-1]*k%mod;
			if (j>1) f[j]=(f[j]+(ll)f[j-2]*(j-1)%mod*i)%mod;
		}
		ans=(ll)ans*f[num[i]]%mod;
	} 
	printf("%d\n",ans);
	return 0;
}