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<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007LL;
in p2(in a){
  return (1LL<<a);
}
in pw(in a, in b, in lm=62){
  a%=mdl;
  if(a<0)
    a+=mdl;
  in r=1;
  for(in i=lm;i>=0;--i){
    r=r*r%mdl;
    if(b&p2(i))
      r=r*a%mdl;
  }
  return r;
}
in inv(in a){
  a%=mdl;
  if(a<0)
    a+=mdl;
  assert(a!=0);
  return pw(a,mdl-2,30);
}
VI fc,invfc;
in ncr(in a, in b){
  if(b==0 || b==a)
    return 1;//even if a<0
  if(b<0 || b>a)
    return 0;
  return fc[a]*invfc[b]%mdl*invfc[a-b]%mdl;
}
void inifc(){
  const in mxfc=1001000;
  fc.resize(mxfc);
  invfc.resize(mxfc);
  fc[0]=fc[1]=invfc[0]=invfc[1]=1;
  for(in i=2;i<mxfc;++i){
    fc[i]=fc[i-1]*i%mdl;
    invfc[i]=invfc[mdl%i]*(mdl-mdl/i)%mdl;
  }
  for(in i=2;i<mxfc;++i){
    invfc[i]*=invfc[i-1];
    invfc[i]%=mdl;
  }
}
void fl(){
  cout<<0<<endl;
  exit(0);
}
in tw(in cnt, in wmix, in wsing){
  in sm=0;
  in cmix=0;
  in wsl=1;
  while(cmix<=cnt){
    if(wsing)
      sm+=pw(wmix,cmix/2)*pw(2,cnt-cmix)%mdl*wsl%mdl*invfc[cmix/2]%mdl;
    else
      sm+=pw(wmix,cmix/2)*wsl%mdl*invfc[cmix/2]%mdl;
    wsl*=cnt-cmix;
    wsl%=mdl;
    ++cmix;
    wsl*=cnt-cmix;
    wsl%=mdl;
    ++cmix;
    wsl*=inv(2);
    wsl%=mdl;
  }
  sm%=mdl;
  return sm;
}
VI pcyc;
VI a;
VI dg;
VI itsz;
VI vis;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  inifc();
  in n;
  cin>>n;
  a.resize(n);
  pcyc.resize(n+1);
  dg.resize(n);
  forn(i,n){
    cin>>a[i];
    --a[i];
    ++dg[a[i]];
    if(dg[a[i]]>2)
      fl();
  }
  itsz.resize(n);
  vis.resize(n);
  queue<in> q;
  forn(i,n){
    if(dg[i]==0){
      vis[i]=1;
      q.push(i);
    }
  }
  while(!q.empty()){
    in u=q.front();
    q.pop();
    if(itsz[a[u]])
      fl();
    itsz[a[u]]=itsz[u]+1;
    if(dg[a[u]]==1){
      vis[a[u]]=1;
      q.push(a[u]);
    }
  }
  VI tit;
  in wys=1;
  forn(i,n){
    tit.clear();
    if(vis[i])
      continue;
    in u=i;
    in ft=-1;
    do{
      vis[u]=1;
      tit.PB(itsz[u]);
      if(itsz[u])
	ft=sz(tit)-1;
      u=a[u];
    }while(u!=i);
    if(ft==-1){
      ++pcyc[sz(tit)];
      continue;
    }
    in cf=ft;
    do{
      in cnt=0;
      do{
	++cnt;
	cf=(cf+1)%sz(tit);
      }while(tit[cf]==0);
      if(cnt<tit[cf])
	fl();
      if(cnt>tit[cf])
	wys=wys*2%mdl;
    }while(cf!=ft);
  }
  forn(i,n+1){
    if(pcyc[i]){
      wys=wys*tw(pcyc[i],i,((i%2==1 && i!=1)?1:0))%mdl;
    }
  }
  cout<<wys<<endl;
  return 0;
}