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<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
const
int Mod=(int)1e9+7;
using namespace std;
int deg[100001],a[100001],num[100001],l[100001],d[100001];
bool vis[100001];
int Fact[100001],Inv[100001];
inline int Pow(int a,int x)
{
    int res=1;
    for(;x;x>>=1,a=a*1ll*a%Mod)
        if(x&1)res=a*1ll*res%Mod;
    return res;
}
queue<int>Q;
inline int C(int x,int y){return Fact[x]*1ll*Inv[y]%Mod*Inv[x-y]%Mod;}
#define x first
#define y second
#define mp make_pair
#define pb push_back

vector<pair<int,int> >Cir;

inline int pr(int n)
{
    return Fact[n<<1]*1ll*Inv[n]%Mod*Pow(Mod+1>>1,n)%Mod;
}
int main()
{
    Fact[0]=1;
    for(int i=1;i<=100000;i++)Fact[i]=Fact[i-1]*1ll*i%Mod;
    Inv[100000]=Pow(Fact[100000],Mod-2);
    for(int i=99999;~i;i--)Inv[i]=Inv[i+1]*(i+1ll)%Mod;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),deg[a[i]]++;
    for(int i=1;i<=n;i++)if(deg[i]>2)return puts("0"),0;
    for(int i=1;i<=n;i++)if(!(d[i]=deg[i]))Q.push(i);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        vis[u]=1;
        if(!--d[a[u]])Q.push(a[u]);
    }
    for(int i=1;i<=n;i++)if(vis[i]&&deg[i]>1)return puts("0"),0;
    for(int i=1;i<=n;i++)if(vis[i]&&!deg[i])
    {
        int x=i,cnt=0;
        for(;vis[x];x=a[x])cnt++;
        l[x]=cnt;
    }
    int ans=1;
    for(int i=1;i<=n;i++)if(!vis[i])
    {
        int x=i,fl=0,tp=1,tot=0;
        for(;!vis[x];x=a[x])++tot,fl|=l[x],vis[x]=1;
        if(!fl){num[tot]++;continue;}
        Cir.clear();
        int p=1;x=i;
        do
        {
            if(l[x])Cir.pb(mp(l[x],p));
            x=a[x];p++;
        }while(x^i);
        Cir.pb(mp(Cir[0].x,Cir[0].y+tot));
        for(int j=1;j<Cir.size();j++)
            if(Cir[j].x>Cir[j].y-Cir[j-1].y)tp=0;
            else if(Cir[j].x^(Cir[j].y-Cir[j-1].y))tp=tp*2ll%Mod;
        ans=ans*1ll*tp%Mod;
    }
    
   // printf("%d\n",ans);
    for(int i=1;i<=n;i++)if(num[i])
    {
        int m=num[i],tp=0;
        for(int j=0;j<=m/2;j++)
        {
            int tp2=1ll*C(m,2*j)*pr(j)%Mod*Pow(i,j)%Mod;
            if(i>1&&(i&1))tp2=tp2*1ll*Pow(2,m-2*j)%Mod;
            tp=(tp+tp2)%Mod;
        }
        ans=ans*1ll*tp%Mod;
    }
    printf("%d\n",ans);
    return 0;
}