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<iostream>
#include<cstdio>
#define MN 100000
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int head[MN+5],cnt=0,n,vis[MN+5],Fa[MN+5],dep[MN+5],c[MN+5],top,in[MN+5],ans=1;
int A,B,C,num[MN+5],vnum,cirnum[MN+5],p[MN+5],inv[MN+5],pw[MN+5],Out[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
	e[++cnt]=(edge){t,head[f]};head[f]=cnt;
	e[++cnt]=(edge){f,head[t]};head[t]=cnt; 
}
void dfs(int x,int fa)
{
	Fa[x]=fa;vis[x]=1;++vnum;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa) 
		{
			if(vis[e[i].to]) A=x,B=e[i].to;
			else dep[e[i].to]=dep[x]+1,dfs(e[i].to,x);
		}
}
inline int lca(int x,int y)
{
	for(;x!=y;x=Fa[x])
		if(dep[x]<dep[y]) swap(x,y);
	return x;	
}
int GetChain(int x,int fa)
{
	int son=0,val=1;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			++son;
			int res=GetChain(e[i].to,x);
			if(res==0) return 0;	
			else val+=res;
		}
	return son>1?0:val;
}
inline int CC(int n,int m){return 1LL*p[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{
	n=read();pw[0]=p[0]=inv[0]=inv[1]=p[1]=1;pw[1]=2;
	for(int i=2;i<=n;++i) p[i]=1LL*p[i-1]*i%mod,inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod,pw[i]=2*pw[i-1]%mod;
	for(int i=2;i<=n;++i) inv[i]=1LL*inv[i-1]*inv[i]%mod;
	for(int i=1,j;i<=n;++i) ++num[j=read()],ins(i,j);
	for(int i=1;i<=n;++i) if(num[i]>2) return 0*puts("0");
	for(int i=1;i<=n;++i) if(!vis[i]) 
	{
		vnum=top=0;dfs(i,0);C=lca(A,B);
		int len=dep[A]+dep[B]-2*dep[C]+1;
		if(len==vnum) {++cirnum[vnum];continue;}
		for(;A!=C;A=Fa[A]) c[++top]=A;c[++top]=C;top=len;
		for(;B!=C;B=Fa[B]) c[len--]=B;
		for(int j=1;j<=top;++j) in[c[j]]=1;
		for(int j=head[c[1]];j;j=e[j].next)
			if(e[j].to==c[2]) 
			{
				if(~j&1) 
					for(int l=1,r=top;l<r;++l,--r)
						swap(c[l],c[r]);
				break;	
			}
		for(int j=1;j<=top;++j)
		{
			Out[j]=0;
			for(int k=head[c[j]];k;k=e[k].next)
				if(!in[e[k].to])
				{
					Out[j]=GetChain(e[k].to,c[j]);
					if(!Out[j]) return 0*puts("0"); 
				}
		}
		int last,way=1;
		for(int j=top;j;--j) if(Out[j]) {last=top-j;break;}
		for(int j=1;j<=top;++j)
		{
			++last;
			if(!Out[j]) continue;
			if(Out[j]>last) return 0*puts("0");
			else if(Out[j]<last) way=way*2%mod;
			last=0;
		}
		ans=1LL*ans*way%mod;
	}
	for(int i=1;i<=n;++i) if(cirnum[i])
	{
		int way=(i==1||i%2==0)?1:pw[cirnum[i]];
		for(int j=1,k=i,i2=mod+1>>1;j<<1<=cirnum[i];++j,k=1LL*k*i%mod,i2=1LL*i2*(mod+1)/2%mod)
		{
			int thway=1LL*CC(cirnum[i],j*2)*CC(j*2,j)%mod*p[j]%mod*i2%mod*k%mod;
			if(i==1||i%2==0);else thway=1LL*thway*pw[cirnum[i]-2*j]%mod;
			way=(way+thway)%mod;
		}
		ans=1LL*ans*way%mod;
	}
	cout<<ans;
	return 0;
}