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:
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007ll
using namespace std;
int n,a[100005],d[100005],c[100005],cnt[100005],f[100005],s[100005];
ll ans=1,dp[100005];
void get(int x){
    int t=0;
    ll res=1;
    cnt[x]=1;
    while(cnt[x]<2){
        x=a[x];
        ++cnt[x],++t;
        if(f[x]){
            if(t<f[x])res=0;
            else if(t>f[x])res=res*2%orz;
            t=0;
        }
    }
    (ans*=res)%=orz;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i),++d[a[i]],c[i]=1;
    queue<int> q;
    for(int i=1;i<=n;++i)if(!d[i])q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        c[x]=0;
        ++cnt[a[x]];
        if(cnt[a[x]]==d[a[x]])q.push(a[x]);
    }
    for(int i=1;i<=n;++i){
        if(d[i]-c[i]>1){
            puts("0");
            return 0;
        }
    }
    for(int i=1;i<=n;++i){
        if(!d[i]){
            int x=i,t=0;
            while(!c[x])x=a[x],++t;
            f[x]=t;
        }
    }
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;++i)if(!cnt[i]&&c[i]&&f[i])get(i);
    for(int i=1;i<=n;++i){
        if(!cnt[i]&&c[i]){
            int x=i,sum=0;
            while(!cnt[x])cnt[x]=1,++sum,x=a[x];
            ++s[sum];
        }
    }
    for(int i=1;i<=n;++i){
        dp[0]=1;
        if(!s[i]) continue;
        int o;
        if(i>1&&(i&1))o=2;
        else o=1;
        for(int j=1;j<=s[i];++j){
            dp[j]=dp[j-1]*o%orz;
            if(j>1)(dp[j]+=dp[j-2]*(j-1)%orz*i)%=orz;
        }
        (ans*=dp[s[i]])%=orz;
    }
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}