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<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int w[101000], Deg[101000], n, chk[101000], Q[101000], tail, head, C[101000];
bool v[101000];
long long Res = 1, D[101000], Mod = 1000000007;
vector<int>E[101000];
int main(){
    int i, x, y, j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
        E[w[i]].push_back(i);
        Deg[w[i]]++;
        if(Deg[w[i]] == 3) goto fail;
    }
    for(i=1;i<=n;i++)if(!Deg[i])Q[++tail] = i;
    while(head < tail){
        x = Q[++head];
        Deg[w[x]]--;
        if(!Deg[w[x]]) Q[++tail] = w[x];
    }
    for(i=1;i<=tail;i++)chk[Q[i]] = 1;
    for(i=1;i<=n;i++){
        if(chk[i] && E[i].size() == 2)goto fail;
        if(chk[i]){
            x=i;
            while(!v[x]){v[x]=true;x=w[x];}
        }
        if(E[i].size() == 2){
            x = E[i][0], y = E[i][1];
            while(E[x].size()*E[y].size()==1) x = E[x][0], y = E[y][0];
            if(E[x].size() + E[y].size() == 2)continue;
            if(E[x].size() + E[y].size() > 2)goto fail;
            Res = Res * 2 % Mod;
        }
    }
    for(i=1;i<=n;i++){
        if(!v[i]){
            x=i;y=0;
            while(!v[x]){y++;v[x]=true;x=w[x];}
            C[y]++;
        }
    }
    for(i=1;i<=n;i++){
        if(!C[i])continue;
        D[0] = 1;
        for(j=1;j<=C[i];j++){
            D[j] = D[j-1];
            if(i!=1&&i%2==1)D[j]=D[j]*2%Mod;
            if(j!=1)D[j] = (D[j] + D[j-2] * (j-1) % Mod * i)%Mod;
        }
        Res = Res * D[C[i]] % Mod;
    }
    printf("%lld\n",Res);
    return 0;
fail:
    puts("0");
}