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;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

const char lf = '\n';

namespace ae86
{
	const int bufl = 1 << 15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0;int b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 100007 , mo = 1000000007;

template<typename T1,typename T2> inline T1 ad(T1 &a,T2 b){return a=a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 dl(T1 &a,T2 b){return a=a>=b?a-b:a-b+mo;}
template<typename T1,typename T2> inline T1 add(T1 a,T2 b){return a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 del(T1 a,T2 b){return a>=b?a-b:a-b+mo;}

lint powa(lint a,lint t)
{
	lint b=1;a=(a+mo)%mo;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a)
{
	return powa(a,mo-2);
}

int n,nex[_]={0},din[_]={0},ed[_]={0};
int isc[_]={0},dlen[_]={0},got[_]={0};
int ccnt[_]={0};

lint ans=1;

void dfs(int x)
{
	int len=0,lasloc=0,firloc=0,firlen=0;
	while(!got[x])
	{
		len++,got[x]=1;
		if(dlen[x])
		{
			if(!firloc)firloc=len,firlen=dlen[x];
			else ans=ans*add<int,int>(dlen[x]<len-lasloc,dlen[x]<=len-lasloc)%mo;
			lasloc=len;
		}
		x=nex[x];
	}
 
	if(!firloc)ccnt[len]++;
	else ans=ans*add<int,int>(firlen<len-lasloc+firloc,firlen<=len-lasloc+firloc)%mo;
}

lint f[_]={0};

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	n=ty();
	for(int i=1;i<=n;i++)nex[i]=ty(),din[nex[i]]++;

	for(int i=1;i<=n;i++)
	{
		if(ed[i])continue;
		int now=i;
		while(!ed[now])ed[now]=i,now=nex[now];
		if(ed[now]!=i)continue;
		while(!isc[now])isc[now]=1,now=nex[now];
	}
	
	for(int i=1;i<=n;i++)if(din[i]>1+isc[i]){cout<<0<<lf;return 0;}

	for(int i=1;i<=n;i++)
	{
		if(din[i])continue;
		int x=i,len=0;
		while(!isc[x])len++,x=nex[x];
		dlen[x]=len;
	}

	for(int i=1;i<=n;i++)if(isc[i] && !got[i])dfs(i);

	for(int i=1;i<=n;i++)
	{
		if(!ccnt[i])continue;
		f[0]=1;
		for(int j=1;j<=ccnt[i];j++)
		{
			if(i>1 && (i&1))f[j]=add(f[j-1],f[j-1]);
			else f[j]=f[j-1];
			if(j>1)ad(f[j],f[j-2]*(j-1)%mo*i%mo);
		}
		ans=ans*f[ccnt[i]]%mo;
	}

	cout<<ans<<lf;

	return 0;
}