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;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

int nx[N],u[N];
vector<int> G[N];
vector<int> cycles[N];
int ct[N],cy[N],ln[N];ll dp[N];
int main(){
  int n; scanf("%d",&n);
  REP(i,n){
    scanf("%d",&nx[i]); nx[i]--;
  }
  int tl=0;
  ll ans=1;
  REP(i,n) if(u[i]==0){
    u[i]=i+1;
    int x=nx[i];
    while(u[x]==0){
      u[x]=i+1; x=nx[x];
    }
    if(u[x]==i+1){
     // printf("%d\n",x+1);
      cycles[tl].pb(x);
      int t=nx[x]; cy[x]=1;
      while(t!=x){
        cy[t]=1; cycles[tl].pb(t); t=nx[t];
       // printf("%d\n",t);
      }
      tl++;
    }
  }
 // printf("h\n");
  REP(i,n) if(cy[i]==0) G[nx[i]].pb(i);
  REP(i,n) if(G[i].size()>1) ans=0;
  if(ans==0) {printf("0\n"); exit(0);}
  FILL(u,0);
  REP(i,n) if(cy[i]){
    ln[i]=0;
    int c=i;
    while(G[c].size()){
      c=G[c][0]; ln[i]++;
    }
  }
 // printf("lol\n");
  REP(i,tl){
    int fl=0;
    REP(j,cycles[i].size()) if(G[cycles[i][j]].size()) fl=1;
    if(fl==0) ct[cycles[i].size()]++;
    else{
      int cr = 0;
      while(G[cycles[i][cr]].size()==0) cr++;
      int tk=cr;
      int lg=0,n=cycles[i].size();
      while(lg<n){
        int pv=(tk-1+n)%n,ex=1;
        while(ln[cycles[i][pv]]==0) pv=(pv-1+n)%n,ex++;//,printf("%d %d\n",pv,);
        if(ln[cycles[i][tk]]>ex) ans=0;
        else if(ln[cycles[i][tk]] <ex) ans=ans*2%mod;
     //   printf("%d %d %d %lld\n",cycles[i][tk]+1,ln[cycles[i][tk]],ex,ans);
        tk=pv; lg+=ex;
      }
    }
  }
  REP(i,n+1) if(ct[i]){
    dp[0]=1;
   // printf("%d %d\n",i,ct[i]);
    REPP(j,1,ct[i]+1){
      if(i%2&&i>1) dp[j]=dp[j-1]*2%mod;
      else dp[j]=dp[j-1];
      if(j>1) dp[j]=(dp[j]+dp[j-2]*(j-1)%mod*i%mod)%mod;
    }
    ans=ans*dp[ct[i]]%mod;
  }
  printf("%lld\n",ans);
  return 0;
}