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<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define NO {puts("0");return 0;}
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=1e5+_;
const int mod=1e9+7;
inline int ad(int x,int y){return x>=mod-y?x-mod+y:x+y;}
inline int re(int x,int y){return x<y?x-y+mod:x-y;}
inline int mu(int x,int y){return (LL)x*y%mod;}
inline int qp(int x,LL y){int r=1;while(y){if(y&1)r=mu(r,x);x=mu(x,x);y>>=1;}return r;}
inline int iv(int x){return qp(x,mod-2);}
inline int dv(int x,int y){return mu(x,qp(y,mod-2));}
inline int gcd(int x,int y){return x?gcd(y%x,x):y;}

int fac[maxn],fac_inv[maxn],Bin[maxn];
int C(int n,int m){return mu(fac[n],mu(fac_inv[m],fac_inv[n-m]));}
void yu()
{
	fac[0]=Bin[0]=1;for(int i=1;i<maxn;i++)fac[i]=mu(fac[i-1],i),Bin[i]=ad(Bin[i-1],Bin[i-1]);
	fac_inv[maxn-1]=iv(fac[maxn-1]);
	for(int i=maxn-2;i>=0;i--)fac_inv[i]=mu(fac_inv[i+1],i+1);
}

int n,ans,to[maxn],du[maxn];
int num[maxn],v[maxn];
int main()
{
	yu();
	scanf("%d",&n); ans=1;
	for(int i=1;i<=n;i++)
		scanf("%d",&to[i]),du[to[i]]++;
	
	for(int i=1;i<=n;i++)
		if(du[i]==0)
		{
			v[i]++; int c=1,x=to[i];
			while(du[x]==1)v[x]++,c++,x=to[x];
			if(v[x])NO v[x]++;
			num[x]=c;
		}
	for(int i=1;i<=n;i++)
		if(du[i]==2&&v[i]==1)
		{
			v[i]++; int c=1,x=to[i];
			while(x!=i)
			{
				v[x]++;
				if(num[x])
				{
					if(c<num[x])NO
					if(c>num[x])ans=ad(ans,ans);
					c=0;
				}
				c++;x=to[x];
			}
			if(c<num[i])NO
			if(c>num[i])ans=ad(ans,ans);
		}
	
	memset(num,0,sizeof(num));
	for(int i=1;i<=n;i++)
		if(du[i]==1&&!v[i])
		{
			v[i]=true; int x=to[i],c=1;
			while(x!=i)v[x]=true,c++,x=to[x];
			num[c]++;
		}
	for(int i=1;i<=n;i++)
		if(num[i])
		{
			int sum=0,inv2=mod/2+1;
			for(int j=0,t=1,inv=1;j+j<=num[i];j++,t=mu(t,i),inv=mu(inv,inv2))
				sum=ad(sum, mu( ((i&1)&&i!=1)?Bin[num[i]-2*j]:1 , mu(t,mu(mu(C(num[i],2*j),inv),mu(fac[2*j],fac_inv[j]))) ) );
			ans=mu(ans,sum);
		}

	printf("%d\n",ans);

	return 0;
}