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>
using namespace std;
int read(){ int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; }
const int N=100005,mod=1e9+7;
int n,a[N],in[N],size[N],vis[N],cro[N]; int q[N],head,tail; int k[N],m; int r[N]; void add(int &x,int y){ if ((x+=y)>=mod) x-=mod; } int sc=0;
int Pre(int k,int n){ return k==1?n:(k-1); }
int solve(int n){
    int ans=1,f=0;
    for (int i=1;i<=n;i++){
        if (k[i]==0) continue;
        f=1; int x=Pre(i,n); while (!k[x]) x=Pre(x,n); int t=(i-x+n)%n;
        if (t==0) t+=n; if (t<k[i]) return 0; if (t>k[i]) ans=2LL*ans%mod;
    }
    if (!f) r[n]++;
    return ans;
}
int dp[N];
int main(){
    n=read();
    memset(in,0,sizeof in);
    for (int i=1;i<=n;i++){
        in[a[i]=read()]++;
        size[i]=1;
    }
    head=tail=0;
    for (int i=1;i<=n;i++){
        if (in[i]>2)
            return puts("0"),0;
        if (in[i]==0)
            q[++tail]=i;
        if (in[i]==2)
            cro[i]=1;
    }
    while (head!=tail){
        int x=q[++head],y=a[x];
        size[y]+=size[x];
        if (!(--in[y]))
            q[++tail]=y;
    }
    for (int i=1;i<=n;i++)
        if (cro[i]&&!in[i])
            return puts("0"),0;
    int ans=1;
    memset(vis,0,sizeof vis);
    for (int i=1;i<=n;i++){
        if (in[i]==0||vis[i])
            continue;
        m=0;
        for (int x=i;!vis[x];x=a[x])
            vis[x]=1,k[++m]=size[x]-1;
        ans=1LL*ans*solve(m)%mod;
    }
    for (int i=1;i<=n;i++)
        if (r[i]>0){
            dp[0]=1,dp[1]=i>1&&(i&1)?2:1;
            for (int j=2;j<=r[i];j++)
                dp[j]=(1LL*(j-1)*i%mod*dp[j-2]+dp[j-1]*(i>1&&(i&1)?2:1))%mod;
            ans=1LL*ans*dp[r[i]]%mod;
        }
    printf("%d\n",ans);
    return 0;
}