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;

const long long mod=1000000007ll;

int main()
{
  int n;
  scanf("%d",&n);
  static int a[100000];
  for(int i=0;i<n;i++){
    scanf("%d",a+i);
    a[i]--;
  }
  vector<vector<int> > e(n);
  for(int i=0;i<n;i++){
    e[a[i]].push_back(i);
  }
  static int b[100000];
  static int T[100000];
  for(int i=0;i<n;i++){
    b[i]=-1;
  }
  int C[100001]={0};
  long long ans=1ll;
  for(int t=0;t<n;t++){
    if(b[t]!=-1){
      continue;
    }
    int i=t;
    while(b[i]==-1){
      b[i]=t;
      i=a[i];
    }
    if(b[i]!=t){
      continue;
    }
    int p=i;
    i=a[i];
    int ini=i;
    int N=0;
    bool F=0;
    do{
      if(e[i].size()>2){
	ans=0ll;
	goto ZERO;
      }
      if(e[i].size()==1){
	T[N]=0;
      }
      else{
	F=1;
	int q=e[i][0]+e[i][1]-p;
	T[N]=1;
	while(e[q].size()>0){
	  if(e[q].size()>1){
	    ans=0ll;
	    goto ZERO;
	  }
	  q=e[q][0];
	  T[N]++;
	}
      }
      N++;
      p=i;
      i=a[i];
    }while(i!=ini);
    if(!F){
      C[N]++;
    }
    else{
      for(int i=0;i<N;i++){
	if(T[i]==0){
	  continue;
	}
	int j=1;
	while(T[(i+N-j)%N]==0){
	  j++;
	}
	if(j>=T[i]+1){
	  ans*=2;
	  ans%=mod;
	}
	else if(j<T[i]){
	  ans=0;
	  goto ZERO;
	}
      }
    }
  }
  for(int i=1;i<=n;i++){
    if(C[i]==0){
      continue;
    }
    vector<long long> dp(C[i]+1);
    dp[0]=1ll;
    dp[1]=(i>1&&i%2==1?2:1);
    for(int j=2;j<=C[i];j++){
      dp[j]=(dp[j-1]*dp[1]%mod+dp[j-2]*(j-1)%mod*i%mod)%mod;
    }
    ans*=dp[C[i]];
    ans%=mod;
  }
 ZERO:
  printf("%lld\n",ans);
  return 0;
}