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 <iostream>
#include <cstdio>
#include <cstring>
#define N 100005
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,a[N],D,IN[N],siz,sum[N],len[N],b[N];
bool inc[N];
ll f[N];
bool vis[N],used[N];
ll calc(ll x){
	return x*(x-1)/2%mod;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),IN[a[i]]++;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int g=i;
		while(!vis[g]) vis[g]=1,g=a[g];
		if(used[g]){
			g=i;
			while(!used[g]) used[g]=1,g=a[g];
			continue;
		}
		int x=a[g];inc[g]=1;b[a[g]]=g;
		while(x!=g) inc[x]=1,b[a[x]]=x,x=a[x];
		g=i;
		while(!used[g]) used[g]=1,g=a[g];
	}
	for(int i=1;i<=n;i++){
		if(inc[i]){if(IN[i]>2) return puts("0"),0;}
		else if(IN[i]>1) return puts("0"),0;
	}
	for(int i=1;i<=n;i++){
		if(!IN[i]){
			int g=i,l=0;
			while(!inc[g]) l++,g=a[g];
			len[g]=l;
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(!vis[i]&&inc[i]){
			int g=i,t=1,L=0;
			if(len[i]) t=0;
			while(!vis[g]){
				if(len[g]) t=0;
				L++;
				vis[g]=1;
				g=a[g];
			}
			if(t) sum[L]++;
		}
	}
	ll ans=1;
	for(int i=1;i<=n;i++){
		ll g=1+(i&1);
		if(i==1) g--;
		f[0]=1;
		for(int p=1;p<=sum[i];p++){
			f[p]=f[p-1]*g;
			if(p>1) f[p]=(f[p]+f[p-2]*(p-1)%mod*i)%mod;
		}
		ans=ans*f[sum[i]]%mod;
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(inc[i]&&len[i]){
			int g=i;
			int x=b[g],L=1;
			while(!len[x]) x=b[x],L++;
			if(len[g]>L) return puts("0"),0;
			if(len[g]<L) ans=ans*2%mod;
			g=a[g];L=1;
			while(g!=i){
				if(!len[g]){
					L++;g=a[g];continue;
				}
				if(len[g]>L) return puts("0"),0;
				if(len[g]<L)
					ans=ans*2%mod;
				L=1;g=a[g];
			}
			g=i;
			while(inc[g]) inc[g]=0,g=a[g];
		}
	}
	printf("%lld",ans);
	return 0;
}