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<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define N 110000
#define mmod 1000000007
#define LL long long
using namespace std;
struct node{LL y,nex;}a[2*N];
LL to[N],du[N],n,fir[N],len,cnt[N],A[N],num,siz,pre[N],l[N],m,pk[N],nt[N];
LL jc[N],ny[N],two[N],ans;
bool v[N],oc[N],b[N],bb[N],has[N];
void ins(LL x,LL y)
{
	a[++len].y=y;a[len].nex=fir[x];fir[x]=len;
}
void dfs(LL x)
{
	A[++num]=x;
	v[x]=1;
	for(LL k=fir[x];k;k=a[k].nex)
	{
		LL y=a[k].y;
		if(v[y]) continue;
		dfs(y);
	}
}
void find_loop(LL x)
{
	siz=0;
	while(1)
	{
		b[x]=1;
		if(b[to[x]])
		{
			LL st=x;
			do{
				siz++;
				oc[x]=1;
				x=to[x];
			}while(x!=st);
			break;
		}
		x=to[x];
	}
}
void solve(LL x)
{
	num=0;
	dfs(x);
	find_loop(x);
	if(siz==num) {cnt[siz]++;return;}
	for(LL i=1;i<=num;i++)
	{
		LL x=A[i];
		if(oc[x]==0 && oc[to[x]]) {if(has[to[x]]) {ans=0;return;}has[to[x]]=1;}
	}
	for(LL i=1;i<=num;i++)
	{
		LL x=A[i],t=0;
		if(du[x]) continue;
		while(oc[x]==0)
		{
			if(bb[x]) 
			{ans=0;return;}
			bb[x]=1;
			x=to[x];
			t++;
		}
		l[x]=t;
		x=to[x];t=1;
		while(has[x]==0) {t++;x=to[x];}
		pre[x]=t;
	}
	for(LL i=1;i<=num;i++)
		if(l[A[i]]>pre[A[i]]) 
		{ans=0;return;}
		else if(l[A[i]]<pre[A[i]]) ans=ans*2%mmod;
	int oo=1;
}
void make(LL k)
{
	LL tmp=0;
	m=cnt[k];
	pk[0]=1;
	for(LL i=1;i<=m;i++) pk[i]=pk[i-1]*k%mmod;
	if(k%2 && k>1) tmp=two[m];
	else tmp=1;
	for(LL i=1;i<=m/2;i++)
	{
		LL t=jc[m]*ny[m-i*2]%mmod*nt[i]%mmod*ny[i]%mmod*pk[i]%mmod;
		if(k%2 && k>1) t=t*two[m-i*2]%mmod;
		tmp=(tmp+t)%mmod;
	}
	ans=ans*tmp%mmod;
}
int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++)
	{
		scanf("%lld",&to[i]);
		ins(i,to[i]);ins(to[i],i);
		du[to[i]]++;
	}
	ans=1;
	for(LL i=1;i<=n;i++) 
	{
		if(v[i]==0) solve(i);
		if(ans==0) {printf("0\n");return 0;}
	}
	jc[0]=jc[1]=ny[0]=ny[1]=two[0]=1;two[1]=2;
	for(LL i=2;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mmod;
		ny[i]=(LL)(-mmod/i)*ny[mmod%i]%mmod;
		two[i]=two[i-1]*2%mmod;
	}
	for(LL i=1;i<=n;i++) ny[i]=ny[i]*ny[i-1]%mmod;
	nt[0]=1;nt[1]=ny[2];
	for(int i=2;i<=n;i++) nt[i]=nt[i-1]*ny[2]%mmod;
	for(LL i=1;i<=n;i++) if(cnt[i]) make(i);
	ans=(ans+mmod)%mmod;
	printf("%lld\n",ans);
	return 0;
}