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>
#define LL long long
#define db double

using namespace std;
const int N=2e5+10,mod=1e9+7,inf=1<<30;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}
int ginv(int a){return fpow(a,mod-2);}
vector<int> e[N];
int n,a[N],v1[N],ti,cr[N],st[N],tp,f[N],g[N],b[N],h[N],fac[N],iac[N];
int C(int a,int b){return b<0||a<b?0:1ll*fac[a]*iac[b]%mod*iac[a-b]%mod;}
bool mk[N];
void dfs(int x)
{
    int nn=e[x].size();
    for(int i=0;i<nn;++i)
    {
	int y=e[x][i];
	dfs(y),f[x]=f[x]?-inf:f[y]+1;
    }
}

int main()
{
    fac[0]=1;
    for(int i=1;i<=N-5;++i) fac[i]=1ll*fac[i-1]*i%mod;
    iac[N-5]=ginv(fac[N-5]);
    for(int i=N-5;i;--i) iac[i-1]=1ll*iac[i]*i%mod;
    n=rd();
    for(int i=1;i<=n;++i) a[i]=rd();
    for(int i=1;i<=n;++i)
	if(!v1[i])
	{
	    ++ti;
	    int x=i;
	    tp=0;
	    while(!v1[x]) v1[x]=ti,st[++tp]=x,x=a[x];
	    if(cr[x]) {mk[x]=1;continue;}
	    if(v1[x]<ti) continue;
	    int cn=0;
	    for(int j=tp;;--j)
	    {
		++cn;
		if(st[j]==x) break;
	    }
	    for(int j=tp;;--j)
	    {
		cr[st[j]]=cn;
		if(st[j]==x) break;
	    }
	    mk[x]=tp>cn;
	}
    ++ti;
    for(int i=1;i<=n;++i)
	if(cr[i]&&v1[i]<ti)
	{
	    int x=i;
	    for(int j=1;j<=cr[i]*2;++j) v1[x]=ti,mk[a[x]]|=mk[x],x=a[x];
	}
    for(int i=1;i<=n;++i)
	if(!cr[i]) e[a[i]].push_back(i);
    int ans=1;
    for(int i=1;i<=n;++i)
	if(cr[i])
	{
	    if(mk[i])
	    {
		int x=i;
		tp=0;
		for(int j=1;j<=cr[i];++j) st[++tp]=x,x=a[x];
		for(int j=1;j<=cr[i];++j) dfs(st[j]);
		for(int j=1;j<=cr[i];++j)
		    if(f[st[j]]<0||f[st[j]]>cr[i]){puts("0");return 0;}
		for(int j=1;j<=cr[i];++j) g[j]=g[j-1]+(bool)f[st[j]];
		for(int j=1;j<=cr[i];++j) g[j+cr[i]]=g[j-1+cr[i]]+(bool)f[st[j]];
		for(int j=cr[i]+1;j<=cr[i]+cr[i];++j)
		{
		    int y=st[j-cr[i]];
		    if(!f[y]) continue;
		    if(cr[i]>1&&g[j-1]-g[j-f[y]]){puts("0");return 0;}
		    ans=1ll*ans*(2-(bool)(g[j-1]-g[j-f[y]-1]))%mod;
		}
	    }
	    else ++b[cr[i]];
	    int x=i,lm=cr[i];
	    for(int j=1;j<=lm;++j) cr[x]=0,x=a[x];
	}
    h[0]=h[1]=1;
    for(int i=2;i<=n;++i) h[i]=1ll*h[i-1]*(2*i-1)%mod;
    for(int i=1;i<=n;++i)
    {
	if(!b[i]) continue;
	int sm=0,dx=1+(i>1&&(i&1));
	for(int j=0;j+j<=b[i];++j)
	    ad(sm,1ll*C(b[i],j+j)*h[j]%mod*fpow(i,j)%mod*fpow(dx,b[i]-j-j)%mod);
	ans=1ll*ans*sm%mod;
    }
    printf("%d\n",ans);
    return 0;
}