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 ha 1000000007
#define fuck {puts("0");return 0;}
using namespace std;

const int N=100010;
int nxt[N],n;
int pre[N][2];
int ring[N],f[N];
bool vis[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",nxt+i);
        if(!pre[nxt[i]][0]) pre[nxt[i]][0]=i;
        else if(!pre[nxt[i]][1]) pre[nxt[i]][1]=i;
        else fuck
    }
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        int j=i,sz=0;
        while(!vis[j])
            vis[j]=1,j=nxt[j];
        int p=j,q;
        do{
            sz++;q=nxt[p];
            if(pre[q][0]!=p)
                swap(pre[q][0],pre[q][1]);
        }while((p=q)!=j);
        bool flag=1;int cur=1;
        do{
            if(!pre[p][1]) continue;
            int a=pre[p][0],b=pre[p][1];
            flag=0;vis[b]=1;
            while(pre[b][0])
            {
                if(pre[a][1]||pre[b][1]) fuck
                a=pre[a][0];b=pre[b][0];vis[b]=1;
            }
            if(!pre[a][1]) (cur<<=1)%=ha;
        }while((p=nxt[p])!=j);
        if(flag) ring[sz]++;
        else ans=1ll*ans*cur%ha;
    }
    for(int i=1;i<=n;i++)
    {
        bool flag=(i&1)&&(i!=1);
        f[0]=1;f[1]=flag+1;
        for(int j=2;j<=ring[i];j++)
            f[j]=(1ll*f[j-2]*(j-1)%ha*i+(f[j-1]<<flag))%ha;
        ans=1ll*ans*f[ring[i]]%ha;
    }
    cout<<ans<<endl;
    return 0;
}