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>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 100010
#define mod 1000000007
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[maxn],deg[maxn],vis[maxn],cir[maxn],len[maxn],sum[maxn];
int ans=1;
void work(int x)
{
    int now=0,fr=0,ed=0,l=0;
    while(cir[x])
    {
        ++now;cir[x]=0;
        if(len[x])
        {
            if(!fr)  fr=ed=now,l=len[x];
            else{
                ans=1ll*ans*((len[x]<now-ed)+(len[x]<=now-ed))%mod;
                ed=now;
            }
        }
        x=a[x];
    }
    if(!fr)  sum[now]++;
    else{
        ans=1ll*ans*((l<now-ed+fr)+(l<=now-ed+fr))%mod;
    }
}
int f[maxn];
void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(deg[i])  continue;
        int x=i,l=0;
        while(!cir[x])
        {
            x=a[x];
            l++;
        }
        len[x]=l;
    }
    for(int i=1;i<=n;i++)  if(cir[i])  work(i);
    for(int i=1;i<=n;i++)
    {
        if(!sum[i])  continue;
        f[0]=1;
        for(int j=1;j<=sum[i];j++)
        {
            if(i>1&&(i&1))  f[j]=(f[j-1]+f[j-1])%mod;
            else            f[j]=f[j-1];
            if(j>1)  f[j]=(f[j]+1ll*f[j-2]*(j-1)%mod*i%mod)%mod;
        }
        ans=1ll*ans*f[sum[i]]%mod;
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)  a[i]=read(),deg[a[i]]++;
    for(int i=1;i<=n;i++)
    {
        if(vis[i])  continue;
        int x=i;
        while(!vis[x])  vis[x]=i,x=a[x];
        if(vis[x]!=i)  continue;
        while(!cir[x])  cir[x]=1,x=a[x];
    }
    for(int i=1;i<=n;i++)
    {
        if((cir[i]&&deg[i]>2)||(!cir[i]&&deg[i]>1))
        {
            puts("0");
            return 0;
        }
    }
    solve();
    printf("%d\n",ans);
    return 0;
}