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>
using namespace std;
#define MAXN 100010
#define MO 1000000007
#define LL long long
int a[MAXN],n,vis[MAXN],du[MAXN],pre[MAXN],cnt[MAXN];
LL fac[MAXN],inv[MAXN],Pow2[MAXN],P[MAXN],ans=1;
LL PowMod(LL a,int b)
{
	LL ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%MO;
		a=a*a%MO;
		b>>=1;
	}
	return ret;
}
LL C(int n,int m)
{
	return fac[n]*inv[m]%MO*inv[n-m]%MO;
}
void Pre()
{
	fac[0]=1;
	for(int i=1;i<MAXN;i++)
		fac[i]=fac[i-1]*i%MO;
	inv[MAXN-1]=PowMod(fac[MAXN-1],MO-2);
	for(int i=MAXN-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%MO;
	Pow2[0]=1;
	for(int i=1;i<MAXN;i++)
		Pow2[i]=2*Pow2[i-1]%MO;
	P[1]=1;
	for(int i=2;i<MAXN;i++)
		P[i]=P[i-1]*(2*i-1)%MO;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		du[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]>2)
		{
			printf("0\n");
			return 0;
		}
		if(du[i]<2||vis[i]) continue;
		int p=i;
		do
		{
			if(vis[p])
			{
				printf("0\n");
				return 0;
			}
			vis[p]=1,pre[a[p]]=p;p=a[p];
		}while(p!=i);
	}
	for(int i=1;i<=n;i++)
		if(!du[i])
		{
			int l1=0,l2=0,p=i;
			while(!vis[p])
			{
				vis[p]=1,p=a[p],l1++;
			}
			do
			{
				p=pre[p];l2++;
			}while(du[p]!=2);
			if(l1<l2) ans=ans*2%MO;
			else if(l1>l2)
			{
				printf("0\n");
				return 0;
			}
		}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			int p=i,c=0;
			while(!vis[p])
			{
				c++;vis[p]=1;
				p=a[p];
			}
			cnt[c]++;
		}
	Pre();
	for(int i=1;i<=n;i++)
		if(cnt[i])
		{
			if((i&1)&&i!=1)
			{
				LL tmp=Pow2[cnt[i]];
				LL x=i;
				for(int j=1;2*j<=cnt[i];(x*=i)%=MO,j++)
					(tmp+=C(cnt[i],2*j)*P[j]%MO*x%MO*Pow2[cnt[i]-2*j]%MO)%=MO;
				ans*=tmp;
				ans%=MO;
			}
			else
			{
				LL tmp=1;
				LL x=i;
				for(int j=1;2*j<=cnt[i];(x*=i)%=MO,j++)
					(tmp+=C(cnt[i],2*j)*P[j]%MO*x%MO)%=MO;
				ans*=tmp;
				ans%=MO;
			}
		}
	printf("%lld\n",ans);
}