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<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=3e5+10,mod=1e9+7;
inline void qr(int &x)
{
	x=0;char c=gc;int f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
	x*=f;
}
void qw(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x/10)qw(x/10);
	putchar(x%10+48);
}
struct edge{int y,next;}e[N<<1];int len,last[N];
void ins(int x,int y){e[++len]=(edge){y,last[x]};last[x]=len;}
int n,fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int ring[N],tot,num[N],a[N];bool v[N];
bool fring(int x,int ed)
{
	if(x==ed){v[x]=1;ring[++tot]=x;return 1;}
	for(int k=last[x],y;k;k=e[k].next)
	{
		y=e[k].y;
		if(fring(y,ed)){v[x]=1;ring[++tot]=x;return 1;}
	}
	return 0;
}
int cnt,c[N],P[N],Q[N],sum[N];
void dfs(int x)
{
	int sz=0;
	for(int k=last[x],y;k;k=e[k].next)
	{
		y=e[k].y;
		if(!v[y])++sz,++cnt,dfs(y);
	}
	if(sz>1){puts("0");exit(0);}
}
int main()
{
	//freopen("dayinf.in","r",stdin);
	//freopen("dayinf.out","w",stdout);
	qr(n);
	for(int i=1;i<=n;i++)qr(a[i]),fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		int p=get(i),q=get(a[i]);
		if(p!=q)fa[p]=q,P[q]|=P[p],Q[q]|=Q[p],ins(a[i],i);
		else P[q]=i,Q[q]=a[i];
	}
	int ans=1;
	for(int i=1;i<=n;i++)if(fa[i]==i)
	{
		tot=0;fring(P[i],Q[i]);
		for(int j=1;j<=tot;j++)cnt=0,dfs(ring[j]),num[j]=cnt;
		reverse(num+1,num+tot+1);
		int fi=-1,s1=1,s2=0,cal=0;
		for(int j=1;j<=tot;j++)if(num[j]){fi=j;break;}
		if(fi==-1){++sum[tot];continue;}
		if(tot==1)
		{
			if(num[fi]>1)return puts("0"),0;
			continue;
		}
		for(int j=tot+1;j<=3*tot;j++)num[j]=num[j-tot];
		for(int j=fi+1;j<fi+num[fi];j++)if(num[j])return puts("0"),0;
		for(int j=fi+num[fi],nxt=j+1;j<fi+tot;j=nxt,nxt=j+1)if(num[j])
		{
			if(j+num[j]-tot>fi){s1=0;return puts("0"),0;}
			for(;nxt<j+num[j];nxt++)if(num[nxt]){s1=0;return puts("0"),0;}
			if(num[j+num[j]])continue;
			s1=1ll*2*s1%mod;
		}
		cal=(cal+s1)%mod;
		if(!num[fi+num[fi]])
		{
			s2=1;
			for(int j=fi+num[fi]+1,nxt=j+1;j<fi+tot;j=nxt,nxt=j+1)if(num[j])
			{
				if(j+num[j]-tot>fi+1){s2=0;return puts("0"),0;}
				for(;nxt<j+num[j];nxt++)if(num[nxt]){s2=0;return puts("0"),0;}
				if(num[j+num[j]])continue;
				s2=1ll*2*s2%mod;
			}
		}
		cal=(cal+s2)%mod;
		ans=1ll*ans*cal%mod;
	}
	for(int i=1;i<=n;i++)if(sum[i])
	{
		if((i&1)&&i!=1)
		{
			c[0]=1;c[1]=2;
			for(int j=2;j<=sum[i];j++)
				c[j]=(c[j-1]*2+1ll*c[j-2]*(j-1)%mod*i%mod)%mod;
			ans=1ll*ans*c[sum[i]]%mod;continue;
		}
		c[0]=1;c[1]=1;
		for(int j=2;j<=sum[i];j++)
			c[j]=(c[j-1]+1ll*c[j-2]*(j-1)%mod*i%mod)%mod;
		ans=1ll*ans*c[sum[i]]%mod;
	}
	qw(ans);puts("");
	return 0;
}