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;

typedef long long LL;
#define N 120000

const LL mod=1000000007;
LL n,ans,a[N],b[N],d[N],cnt[N],f[N];
bool vis[N];

int main(){
	scanf("%lld",&n);
	for (LL i=1;i<=n;++i){
		scanf("%lld",a+i);
		++d[a[i]];
	}
	for (LL i=1;i<=n;++i){
		if (d[i]>2){puts("0"); return 0;}
		if (d[i]<2||vis[i]) continue;
		vis[i]=1; b[a[i]]=i;
		for (LL j=a[i];j!=i;j=a[j]){
			if (vis[j]){puts("0"); return 0;}
			vis[j]=1; b[a[j]]=j;
		}
	}
	ans=1;
	for (LL i=1;i<=n;++i)
		if (!d[i]){
			LL j=i,len1=0,len2=1;
			for (;!vis[j];j=a[j]){vis[j]=1; ++len1;}
			for (j=b[j];d[j]<2;j=b[j]) ++len2;
			if (len1>len2){puts("0"); return 0;}
			if (len1<len2) ans=ans*2%mod;
		}
	for (LL i=1;i<=n;++i)
		if (!vis[i]){
			vis[i]=1;
			LL len=1;
			for (LL j=a[i];!vis[j];j=a[j]){vis[j]=1; ++len;}
			++cnt[len];
		}
	for (LL i=1;i<=n;++i){
		LL t=i!=1&&(i&1)?2:1;
		f[0]=1; f[1]=t;
		for (int j=2;j<=cnt[i];++j) f[j]=(f[j-1]*t+f[j-2]*(j-1)%mod*i)%mod;
		ans=ans*f[cnt[i]]%mod;
	}
	printf("%lld\n",ans);
	
	return 0;
}