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;
#define ll long long
const int N=110000,mod=1000000007;
int n,ans;
int jc[N],njc[N],bir[N],nbir[N];
int a[N],fa[N],du[N],num[N],vis[N],tail[N],rem[N];
int f[N][2][2];
vector<int>vec[N],v1;
int qpow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=(ll)ret*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}
	return ret;
}
void init()
{
	for(int i=1;i<=n;i++)fa[i]=i;
	jc[0]=njc[0]=bir[0]=nbir[0]=1;
	for(int i=1;i<=n;i++)
	{
		jc[i]=(ll)jc[i-1]*i%mod;
		bir[i]=bir[i-1]*2%mod;
	}
	njc[n]=qpow(jc[n],mod-2);
	nbir[n]=qpow(bir[n],mod-2);
	
	for(int i=n-1;i>=1;i--)
	{
		njc[i]=(ll)njc[i+1]*(i+1)%mod;
		nbir[i]=nbir[i+1]*2%mod;
	}
}
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
void quit(){puts("0");exit(0);}
void ins(int x)
{
	if(!tail[x])return;
	if(rem[x]<tail[x])quit();
	else if(rem[x]>tail[x])ans=ans*2%mod;
}
int main()
{
	//freopen("tt.in","r",stdin);
	scanf("%d",&n);
	init();
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(find(i)!=find(a[i]))
			fa[find(i)]=find(a[i]);
		du[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]>2)quit();
		vec[find(i)].push_back(i);
	}
	ans=1;
	for(int i=1,sz;i<=n;i++)if(sz=vec[i].size())
	{
		int p=-1;
		for(int j=0;j<sz;j++)
			if(du[vec[i][j]]==2)p=vec[i][j];
		if(p==-1)num[sz]++;
		else
		{
			int t=0,p1=a[p];
			vis[p]=++t;
			while(p1!=p)
			{
				if(vis[p1])quit();
				vis[p1]=++t;
				p1=a[p1];
			}
			for(int j=0,cnt;j<sz;j++)
				if(du[p1=vec[i][j]]==0)
				{
					cnt=0;
					while(!vis[p1])
					{
						cnt++;
						if(du[p1]==2)quit();
						p1=a[p1];
					}
					tail[p1]=cnt;
				}
			int now=0;p1=p;
			for(int j=1;j<=t*2;j++,p1=a[p1])
			{
				if(tail[p1])
					rem[p1]=max(rem[p1],now+1),now=0;
				else now++;
			}
			v1.clear();
			ins(p);p1=a[p];
			while(p1!=p)
			{
				ins(p1);
				p1=a[p1];
			}
		}
	}
	for(int i=1;i<=n;i++)if(num[i])
	{
		int t=0,now=1;
		for(int j=0;j<=num[i];j+=2)
		{
			int t1=(ll)jc[num[i]]*njc[num[i]-j]%mod*njc[j>>1]%mod*nbir[j>>1]%mod*now%mod;
			if((i&1)&&i!=1)t1=(ll)t1*bir[num[i]-j]%mod;
			t=(t+t1)%mod;
			now=(ll)now*i%mod;
		}
		ans=(ll)ans*t%mod;
	}
	printf("%d\n",ans);
	return 0;
}