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<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 100005
#define M 200005
#define Mo 1000000007

using namespace std;
int i,j,m,n,p,k,a[N],chun[N],deg[N],D[N],vis[N],Q[N],size[N],tot,ans,Qt[N];
int fac[N],inv[N];
vector<int>tree[N],v[N];
void work(int x)
{
		int i;
		Q[0]=0;
		for (i=x;!vis[x];x=a[x]) vis[x]=1,Q[++Q[0]]=x; 
		for (i=1;i<=Q[0];++i) if (size[Q[i]]) break;
		if (i<=Q[0]) 
		{
				++tot; 
				for (i=1;i<=Q[0];++i) tree[tot].pb(Q[i]);
		}
		else chun[Q[0]]++;
}
void jia(int &x,int y)
{
		x+=y; if (x>=Mo) x-=Mo;
}
int dp()
{
		int i,la=0,lb=0,fa=1;
		for (i=1;i<=Qt[0];++i)
			if (size[Qt[i]])
			{
					int na=i+size[Qt[i]]-1,nb=i+size[Qt[i]],ga=0;
					if (la<i) jia(ga,fa);
					if (lb&&lb<i) jia(ga,fa);
					fa=ga; la=na; lb=nb;
			}
		int now=0;
		if (la<=Qt[0]) jia(now,fa);
		if (lb<=Qt[0]) jia(now,fa);
		return now;
}
int power(int x,int y)
{
		int sum=1;
		for (;y;y>>=1)
		{
			if (y&1) sum=1ll*sum*x%Mo;
			x=1ll*x*x%Mo;
		}
		return sum;
}
int C(int x,int y)
{
		return 1ll*fac[x]*inv[y]%Mo*inv[x-y]%Mo;
}
void pre()
{
	fac[0]=inv[0]=1;
	for (i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%Mo,inv[i]=power(fac[i],Mo-2); 
}
int Count(int x)
{
		Q[0]=0;
		int i;
		for (i=0;i<(int)tree[x].size();++i) Q[++Q[0]]=tree[x][i];
		if (Q[0]==1)
		{
				if (size[Q[1]]==1) return 1;
				return 0;
		}
		for (i=1;i<=Q[0];++i) if (size[Q[i]]) break;
		Qt[0]=0;
		for (j=i;j>=1;--j) Qt[++Qt[0]]=Q[j];
		for (j=Q[0];j>i;--j) Qt[++Qt[0]]=Q[j]; 
		return dp();
}
int main()
{
	pre();
	scanf("%d",&n);
	for (i=1;i<=n;++i) scanf("%d",&a[i]),v[i].pb(a[i]),deg[a[i]]++;
	for (i=1;i<=n;++i) D[i]=deg[i];
	for (i=1;i<=n;++i) if (!deg[i]) Q[++Q[0]]=i;
	for (i=1;i<=n;++i) if (deg[i]>2)
	{
			puts("0");
			return 0;
	}
	int l;
	for (l=1;l<=Q[0];++l)
	{
			int p=Q[l]; vis[p]=1;
			size[p]++;
			for (i=0;i<(int)v[p].size();++i)
			{
					int k=v[p][i];
					deg[k]--; size[k]+=size[p];
					if (deg[k]==0) Q[++Q[0]]=k;
			}
	}
	for (i=1;i<=n;++i) if (vis[i]&&D[i]==2)
	{	
			puts("0");
			return 0;
	}
	for (i=1;i<=n;++i) if (!vis[i]) work(i);
	ans=1;
	for (i=1;i<=n;++i)
			if (chun[i])
			{
					int now=0;
					for (j=0;j<=chun[i];j+=2)
					jia(now,
					1ll*((i>1&&(i&1))?power(2,chun[i]-j):1)*C(chun[i],j)%Mo*C(j,j/2)%Mo*fac[j/2]%Mo*power(power(2,j/2),Mo-2)%Mo*power(i,j/2)%Mo);
					ans=1ll*ans*now%Mo;
			}
	for (i=1;i<=tot;++i) 
	{
		int now=Count(i);
		ans=1ll*ans*now%Mo;
	}
	printf("%d\n",ans);
	return 0;
}