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>
#include<cstring>
using namespace std;
const int N=5e5+500,mod=1000000007;
int p[N],stack[N],inq[N],vis[N],inring[N],len[N],tmp[N],cnt[N],top,n,rd[N],fac[N],ifac[N],inv[N],pw2[N],ipw2[N];
void dfs(int u)
{
    stack[++top]=u,inq[u]=1,vis[u]=1;
    int v=p[u];
    if(inq[v])
    {
        int t=top;stack[top+1]=0;
        while(stack[top+1]!=v)inring[stack[top--]]=1;
        top=t;
    }
    if(!vis[v])dfs(v);inq[u]=0;
}
void getdep(int u)
{
    int dep=0;while(!inring[u])++dep,u=p[u];
    len[u]=dep;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",p+i),rd[p[i]]++;
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
    for(int i=1;i<=n;i++)if(rd[i]>=2+inring[i]){puts("0");return 0;}
    for(int i=1;i<=n;i++)if(!rd[i])getdep(i);
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        if(!inring[i])continue;
        int u=i,tn=0,iscir=!len[u];inring[u]=0;tmp[++tn]=u;
        while(p[u]!=i)u=p[u],tmp[++tn]=u,iscir&=!len[u],inring[u]=0;
        if(iscir){++cnt[tn];continue;}
        int lst=0;
        for(int j=tn;j>=1;j--)if(len[tmp[j]]){lst=j-tn;break;}
        for(int j=1;j<=tn;j++)
        {
            if(!len[tmp[j]])continue;
            if(j-len[tmp[j]]<lst){puts("0");return 0;}
            if(j-len[tmp[j]]>lst)ans=(ans<<1)%mod;
            lst=j;
        }
    }
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    inv[1]=1;for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    ifac[0]=1;for(int i=1;i<=n;i++)ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
    pw2[0]=1;for(int i=1;i<=n;i++)pw2[i]=(pw2[i-1]<<1)%mod;
    ipw2[0]=1;for(int i=1;i<=n;i++)ipw2[i]=(ipw2[i-1]&1)?((ipw2[i-1]+mod)>>1):(ipw2[i-1]>>1);
    for(int i=1;i<=n;i++)
    {
        if(!cnt[i])continue;
        int tn=cnt[i];int s=0,pw=1;
        for(int j=0;j*2<=tn;j++)
        {
            int t=1ll*ifac[tn-2*j]*ifac[j]%mod*ipw2[j]%mod*pw%mod;
            if((i&1)&&i!=1)t=1ll*t*pw2[tn-2*j]%mod;
            s=(s+t)%mod;pw=1ll*pw*i%mod;
        }
        ans=1ll*ans*s%mod*fac[tn]%mod;
    }
    cout<<ans<<endl;
}