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 <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <map>

const int64_t MOD=1e9+7;
const int64_t INV2=5e8+4;

int vis[100005];

int next[100005];
std::vector<int> prev[100005];
int buddy[100005];
int root[100005];
bool cycle[100005];

int64_t inv[100005];

void fail(){
  printf("0\n");
  exit(0);
}

void dfs_root(int node){
  root[node]=node;
  if(!root[next[node]]) dfs_root(next[node]);
  root[node]=root[next[node]];
}

int main(){
  int N;
  scanf("%d",&N);
  inv[1]=1;
  for(int i=2;i<=N;i++){
    inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
  }
  for(int i=1;i<=N;i++){
    scanf("%d",&next[i]);
    prev[next[i]].push_back(i);
  }
  for(int i=1;i<=N;i++){
    if(prev[i].size()>2) fail();
  }
  for(int i=1;i<=N;i++){
    int layer[4];
    int layer_cnt=0;
    for(int x:prev[i]) layer[layer_cnt++]=x;
    while(layer_cnt==2){
      int a=layer[0],b=layer[1];
      //printf("LAYER %d:%d\n",a,b);
      if(buddy[a]||buddy[b]){
	assert(buddy[a]==b);
	assert(buddy[b]==a);
	break;
      }
      buddy[a]=b,buddy[b]=a;
      
      layer_cnt=0;
      for(int x:prev[a]) layer[layer_cnt++]=x;
      for(int x:prev[b]) layer[layer_cnt++]=x;
    }
    if(layer_cnt>2) fail();
  }
  std::map<int,int> pures;
  for(int i=1;i<=N;i++){
    if(!root[i]) dfs_root(i);
  }
  for(int i=1;i<=N;i++){
    if(root[i]==i){
      bool ispure=true;
      int length=0;
      int j=i;
      do{
	if(prev[j].size()>1) ispure=false;
	cycle[j]=true;
	length++;
	j=next[j];
      }while(j!=i);
      
      if(ispure){
	pures[length]++;
      }
    }
  }
  int64_t ans=1;
  for(int i=1;i<=N;i++){
    if(cycle[i]&&buddy[next[i]]&&!buddy[i]){
      ans=ans*2%MOD;
    }
  }
  for(auto pair:pures){
    int64_t len=pair.first,cnt=pair.second;
    //printf("PURE %ld x%ld\n",len,cnt);
    int64_t ac=1;
    if(len%2==1&&len>1){
      for(int i=0;i<cnt;i++){
	ac=ac*2%MOD;
      }
    }
    int64_t sum=ac;
    //printf(" %ld",ac);
    int pairs=0;
    while(cnt>1){
      ac=(ac*len)%MOD*((cnt*(cnt-1)/2)%MOD)%MOD*inv[++pairs]%MOD;
      cnt-=2;
      if(len%2==1&&len>1){
	ac=ac*INV2%MOD*INV2%MOD;
      }
      sum=(sum+ac)%MOD;
      //printf("+%ld",ac);
    }
    //printf(" => %ld\n",sum);
    ans=ans*sum%MOD;
  }
  printf("%ld\n",ans);
  return 0;
}